证明算法的

‘壹’ 怎么证明由三种基本结构所构成的算法可以解决任何复杂问题

三种基本结构化结构：顺序、选择、循环。证明如下：

一、很多书籍确确实实的说明指出，这三种结构可以解决一切复杂的算法问题是已经证明了的。

二、算法过程就是一个步骤一个步骤、一条指令一条指令按照程序执行的过程，所以顺序结构很自然的就是算法的一个最基本的特性。

三、我们在解决问题时，由于对一些事实情况把握不太确定（逻辑学告诉我们思维必须确定才能进行正确的思维，否则会发生前后矛盾的情况，这也是一个良好算法的要求），所以如果不进行正确的判断的话，就不能轻易进入下一步骤。

由此当算法执行到某一步骤时，如果要对某些情况进行判断，才能进入下一步的执行，那么选择结构就是必须的了。它正是判断了之后，再确定该执行哪些步骤。

四、循环结构是非必需的，它可有前两种结构构成。

所以，总结起来：任何算法它都是机械的一系列步骤，并且要求每一步都是确定的，当执行完这一步骤后，它就要确定下一步骤，如果根据算法对象已经知道下一步该执行什么了，就不需要再判断直接进入下一步。

但是当对这些算法对象的情况不确定时，我们就要判断并选择一些已经确定好操作对象的步骤。这也是问题的一个最根本的特性，就是我们提出问题的原因。因为思维遇到阻碍，就需要判断，只有确定后才能继续正确思维，才能解决问题。

‘贰’ 算法的正确性证明方法一: 循环不变量

在之前的一篇文章里写到 算法的正确性 的概念以及它的作用，下面就来写写循环不变量在算法的正确性证明中的用法。

在使用循环的算法里，可以通过循环不变量证明其正确性。
所谓循环不变量是指一种在整个循环过程中保持不变的性质，它必须在以下3种情况下均保持不变，且该性质源困在循环终止后能证明算法的正确性。

接下来就 归并排序（Merge sort） 中的 merge 函数来说明一下循环不变量

先解释一下这个函数的作用，sld 和 srd 为已排序数组，大小分别为 lc 和 rc，循环 tc (lc + rc) 次把它们的元素进行比较并复制到新分配的数组 md 中，那要怎么证明这个算法的正确性呢。

让我们先设定循环不变量，然后看8-18行的循环能否在以上3种情况都满足这个循环不变量。

结束时循环不变量给了我们一个有用信息，此迟氏时 md 已经把 sld 和 srd 中全部元素合并排序了， 从雹旦念而证明了算法的正确性。

‘叁’ 如何用归纳法证明算法的时间复杂度 t(n)<=T(n/5)+T(3n/4)+cn<=20cn

1.假设n=1时候，验证
t(1)<=T(1/5)+T(3/4)+c<=20c
2.假设当n=k-1（或者n<=k-1，这两个具体情况具体分析)时候满足：
t(k-1)<=T(k-1/5)+T(3(k-1)/4)+c(k-1)<=20c(k-1)
当n=k时候，
从各个方面分析,t(k-1)与t(k)d的关系，T(k-1)与T(k)的关系，以及c的取值什么的。如果这题目正常的话就应该会的出值了。

‘肆’ 贪心算法的证明方法

贪心算法的基本思路如下：
1.建立数学模型来描述问题。
2.把求解的问题分成若干个子问题。
3.对每一子问题求解，得到子问题的局部最优解。
4.把子问题的解局部最优解合成原来解问题的一个解。
----------------------------------------------
其实归纳起来也就一个类。其他的都是分支

‘伍’ 图论算法的论证

有向无回路图又称为dag。对这种有向无回路图的拓扑排序的结果为该图所有顶点的一个线性序列，满足如果G包含(u,v)，则在序列中u出现在v之前（如果图是有回路的就不可能存在这样的线性序列）。一个图的拓扑排序可以看成是图的所有顶点沿水平线排成的一个序列，使得所有的有向边均从左指向右。因此，拓扑排序不同于通常意义上对于线性表的排序。
有向无回路图经常用于说明事件发生的先后次序，图1给出一个实例说明早晨穿衣的过程。必须先穿某一衣物才能再穿其他衣物（如先穿袜子后穿鞋），也有一些衣物可以按任意次序穿戴（如袜子和短裤）。
图中说明经拓扑排序的结点以与其完成时刻相反的顺序出现。因为深度优先搜索的运行时间为θ(V+E)，每一个v中结点插入链表需占用的时间为θ(1)，因此进行拓扑排序的运行时间θ(V+E)。
为了证明算法的正确性，我们运用了下面有关有向无回路图的重要引理。 有向图G无回路当且仅当对G进行深度优先搜索没有得到反向边。
证明：→：假设有一条反向边(u,v)，那么在深度优先森林中结点v必为结点u的祖先，因此G中从v到u必存在一通路，这一通路和边(u,v)构成一个回路。
←：假设G中包含一回路C，我们证明对G的深度优先搜索将产生一条反向边。设v是回路C中第一个被发现的结点且边(u,v)是C中的优先边，在时刻d[v]从v到u存在一条由白色结点组成的通路，根据白色路径定理可知在深度优先森林中结点u必是结点v的后裔，因而(u,v)是一条反向边。（证毕） Topological_Sort(G)算法可产生有向无回路图G的拓扑排序
证明
假设对一已知有问无回路图G=(V,E)运行过程DFS以确定其结点的完成时刻。那么只要证明对任一对不同结点u,v∈V，若G中存在一条从u到v的有向边，则f[v]<F[U]即可。考虑过程DFS(G)所探寻的任何边(U,V)，当探寻到该边时，结点V不可能为灰色，否则V将成为U的祖先，(U,V)将是一条反向边，和引理1矛盾。
因此，v必定是白色或黑色结点。若v是白色，它就成为u的后裔，因此f[v]<F[U]。若V是黑色，同样F[V]<F[U]。这样一来对于图中任意边(U,V)，都有F[V]<F[U]，从而定理得证。（证毕）