计算机算法设计与分析 复习资料

第一章

（1）最坏情况下的时间复杂性

Tmax(n) = max{ T(I) | size(I)=n }

（2）最好情况下的时间复杂性

Tmin(n) = min{ T(I) | size(I)=n }

（3）平均情况下的时间复杂性

Tavg(n) =

其中I是问题的规模为n的实例，p(I)是实 例I出现的概率。

规则O(f(n))+O(g(n)) = O(max{f(n),g(n)}) 的证明：

对于任意f1(n)  O(f(n)) ，存在正常数c1和自然数n1，使得对所有n n1，有f1(n)  c1f(n) 。

类似地，对于任意g1(n)  O(g(n)) ，存在正常数c2和自然数n2，使得对所有n n2，有g1(n)  c2g(n) 。

令c3=max{c1, c2}， n3 =max{n1, n2}，h(n)= max{f(n),g(n)} 。

则对所有的 n  n3，有

f1(n) +g1(n)  c1f(n) + c2g(n)

 c3f(n) + c3g(n)= c3(f(n) + g(n))

 c32 max{f(n),g(n)}

= 2c3h(n) = O(max{f(n),g(n)}) .

算法分析的基本法则

非递归算法：

（1）for / while 循环

循环体内计算时间*循环次数；

（2）嵌套循环

循环体内计算时间*所有循环次数；

（3）顺序语句

各语句计算时间相加；

（4）if-else语句

if语句计算时间和else语句计算时间的较大者。

第二章 递归与分治策略

递归算法总体思想:将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。

分治法的设计思想是，将一个难以直接解决的大问题，

分割成一些规模较小的相同问题，以便各个击破，

分而治之。

直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。

nIsizeITIp)()()(边界条件与递归方程是递归函数的二个要素

优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。

缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。

解决方法：在递归算法中消除递归调用，使其转化为非递归算法。

1、采用一个用户定义的栈来模拟系统的递归调用工作栈。该方法通用性强，但本质上还是递归，只不过人工做了本来由编译器做的事情，优化效果不明显。

2、用递推来实现递归函数。

3、通过变换能将一些递归转化为尾递归，从而迭代求出结果。

第三章 动态规划

基本思想是将待求解问题分解成若干个子问题，但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。

基本步骤

找出最优解的性质，并刻划其结构特征。

递归地定义最优值。

以自底向上的方式计算出最优值。

根据计算最优值时得到的信息，构造最优解。

基本要素

一、 最优子结构

矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。

在分析问题的最优子结构性质时，所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。

利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。

二、重叠子问题

递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质。

动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。

通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间，从而获得较高的解题效率。

三、备忘录方法

备忘录方法的控制结构与直接递归方法的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同子问题的重复求解。 第四章 贪心算法

基本要素

1、贪心选择性质

所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。

2、最优子结构性质

当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。

第五章 回溯法

有许多问题，当需要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时，往往要使用回溯法。

回溯法的基本做法是搜索，或是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题。

回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。

用回溯法解题的算法框架

（1）递归回溯

（2）迭代回溯

（3）子集树算法框架

（4）排列树算法框架

问题的解空间

问题的解向量：回溯法希望一个问题的解能够表示成一个n元式(x1,x2,…,xn)的形式。

显约束：对分量xi的取值限定。

隐约束：为满足问题的解而对不同分量之间施加的约束。

解空间：对于问题的一个实例，解向量满足显式约束条件的所有多元组，构成了该实例的一个解空间。

回溯法的基本思想

(1)针对所给问题，定义问题的解空间；

(2)确定易于搜索的解空间结构；

(3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

常用剪枝函数：

用约束函数在扩展结点处剪去不满足约束的子树；

用限界函数剪去得不到最优解的子树。

用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为O(h(n))。而显式地存储整个解空间则需要O(2h(n))或O(h(n)!)内存空间。

效率分析：

通过前面具体实例的讨论容易看出，回溯算法的效率在很大程度上依赖于以下因素：

(1)产生x[k]的时间；

(2)满足显约束的x[k]值的个数；

(3)计算约束函数constraint的时间；

(4)计算上界函数bound的时间；

(5)满足约束函数和上界函数约束的所有x[k]的个数。

好的约束函数能显著地减少所生成的结点数。但这样的约束函数往往计算量较大。因此，在选择约束函数时通常存在生成结点数与约束函数计算量之间的折衷

第六章 分支界限法；

分支限界法与回溯法

（1）求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。

（2）搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。

分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。

常见的两种分支限界法

（1）队列式(FIFO)分支限界法

按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。

（2）优先队列式分支限界法

按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。

第七章 随机化算法

第八章 线性规划与网络流

变量满足约束条件(8.2)-(8.5)式的一组值称为线性规划问题的一个可行解。

所有可行解构成的集合称为线性规划问题的可行区域。

使目标函数取得极值的可行解称为最优解。

在最优解处目标函数的值称为最优值。

有些情况下可能不存在最优解。

通常有两种情况：

(1)根本没有可行解，即给定的约束条件之间是相互排斥的，可行区域为空集；

(2)目标函数没有极值，也就是说在n 维空间中的某个方向上，目标函数值可以无限增大，而仍满足约束条件，此时目标函数值无界。

线性规划基本定理：如果线性规划问题有最优解，则必有一基本可行最优解。

上述定理的重要意义在于，它把一个最优化问题转化为一个组合问题，即在(8.2)

-(8.5)式的m+n个约束条件中，确定最优解应满足其中哪n个约束条件的问题。

由此可知，只要对各种不同的组合进行测试，并比较每种情况下的目标函数值，直到找到最优解。

单纯形算法的特点是：

（1）只对约束条件的若干组合进行测试，测试的每一步都使目标函数的值增加；

（2）一般经过不大于m或n次迭代就可求得最优解。

当线性规划问题中没有不等式约束(8.2)和(8.4)式，而只有等式约束(8.3)和变量非负约束(8.5)时，称该线性规划问题具有标准形式。

为便于讨论，不妨先考察一类更特殊的标准形式线性规划问题。这一类线性规划问题中，每一个等式约束中，至少有一个变量的系数为正，且这个变量只在该约束中出现。

在每一约束方程中选择一个这样的变量，并以它作为变量求解该约束方程。这样选出来的变量称为左端变量或基本变量，其总数为m个。剩下的n-m个变量称为右端变量或非基本变量。

这一类特殊的标准形式线性规划问题称为约束标准型线性规划问题。

单纯形算法的第1步：选出使目标函数增加的非基本变量作为入基变量。

单纯形算法的第2步：选取离基变量。

单纯形算法的第3步：转轴变换。转轴变换的目的是将入基变量与离基变量互调位置。

单纯形算法的第4步：转回并重复第1步，进一步改进目标函数值。

不断重复上述过程，直到z行的所有非基本变量系数都变成负值为止。这表明目标函数不可能再增加了。

单纯形算法计算步骤如下：

步骤1：选入基变量。

如果所有cj0，则当前基本可行解为最优解，计算结束。

否则取ce>0相应的非基本变量xe为入基变量。

步骤2：选离基变量。

对于步骤1选出的入基变量xe ，如果所有aie0 ，则最优解无界，计算结束。

否则计算

选取基本变量xk为离基变量。

新的基本变量下标集为

新的非基本变量下标集为

步骤3：作转轴变换。

步骤4：转步骤1。