算法导论复习资料一、选择题：第一章的概念、术语。
二、考点分析：1、复杂度的渐进表示，复杂度分析。
2、正确性证明。
考点：1）正确性分析（冒泡，归并，选择）；2）复杂度分析（渐进表示O，Ｑ，©，替换法证明，先猜想，然后给出递归方程）。
循环不变性的三个性质：1）初始化：它在循环的第一轮迭代开始之前，应该是正确的；2）保持：如果在循环的某一次迭代开始之前它是正确的，那么，在下一次迭代开始之前，它也应该保持正确；3）当循环结束时，不变式给了我们一个有用的性质，它有助于表明算法是正确的。
插入排序算法：INSERTION-SORT(A)1 for j ←2 to length[A]2 do key ←A[j]3 ▹Insert A[j] into the sorted sequence A[1，j - 1].4 i ←j - 15 while i > 0 and A[i] > key6 do A[i + 1] ←A[i]7 i ←i - 18 A[i + 1] ←key插入排序的正确性证明：课本11页。
归并排序算法：课本17页及19页。
归并排序的正确性分析：课本20页。
3、分治法（基本步骤，复杂度分析）。
——许多问题都可以递归求解考点：快速排序，归并排序，渐进排序，例如：12球里面有一个坏球，怎样用最少的次数找出来。
（解：共有24种状态，至少称重3次可以找出不同的球）不是考点：线性时间选择，最接近点对，斯特拉算法求解。
解：基本步骤：一、分解：将原问题分解成一系列的子问题；二、解决：递归地解各子问题。
若子问题足够小，则直接求解；三、合并：将子问题的结果合并成原问题的解。
复杂度分析：分分治算法中的递归式是基于基本模式中的三个步骤的，T(n)为一个规模为n的运行时间，得到递归式T(n)=Q(1) n<=cT(n)=aT(n/b)+D(n)+C(n) n>c附加习题：请给出一个运行时间为Q(nlgn)的算法，使之能在给定的一个由n个整数构成的集合S 和另一个整数x时，判断出S中是否存在有两个其和等于x的元素。
4、动态规划（最优子结构性质，自底向上填表计算最优解值（即最长公共子序列），导出最优解）。
考点：最优子结构性质，自底向上填表计算最优解值，导出最优解。
a）动态规划算法设计的4个步骤：1）描述最优解的结构；2）递归定义最优解的值；3）按自底向上的方式计算最优解的值；4）由计算出的结果构造一个最优解。
b）最优子结构遵循的共同模式：1）问题的一个解可以是做一个选择，做这种选择可能会得到一个或多个有待解决的子问题；2）假设对一个给定的问题，已知的是一个可以导致最优解的选择，不必关心如何确定这个选择，尽管假定它是已知的；3）在已知这个选择后，要确定哪些子问题会随之发生，以及如何最好地描述所得到的子问题的空间；4）利用一种―剪切粘贴法‖，来证明在问题的一个最优解中，使用的子问题的解本身也必须是最优的。
备注：A problem exhibitsoptimal substructure if an optimal solution to the problem contains within it optimal solutions tosubproblems.Whenever a problem exhibits optimal substucture it is a good clue that dynamic programming might apply.c ）最长公共子序列的算法：这里以两个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}为输入，注意课本211页的自底向上填表方法。
LCS-LENGTH(X, Y) 注：此程序运行时间为O （mn ），每个表项的计算时间为O （1） 1 m ← length[X]2 n ← length[Y]3 for i ← 1 to m4 do c[i, 0] ← 05 for j ← 0 to n6 do c[0, j] ← 07 for i ← 1 to m8 do for j ← 1 to n9do if xi = yj 10then c[i, j] ← c[i - 1, j - 1] + 1 11b[i, j] ← ―=" 12else if c[i - 1, j] ≥ c[i, j - 1] 13 then c[i, j] ← c[i - 1, j]14 b[i, j] ← "↑"15 else c[i, j] ← c[i, j - 1]16 b[i, j] ← " ← "17 return c and bPRINT-LCS(b, X, i, j) 注：此程序运行时间为O （m+n ）1 if i = 0 or j = 02 then return3 if b[i, j] = "="4 then PRINT-LCS(b, X, i - 1, j - 1)5 print xi6 elseif b[i, j] = "↑"7 then PRINT-LCS(b, X, i - 1, j)8 else PRINT-LCS(b, X, i, j - 1)d ）矩阵链乘法的算法：参照课本上的矩阵链表得出矩阵相乘的最小算法。
}],1[],[{min ],[1j k i jk i p p p j k m k i m j i m -<≤+++=MATRIX-CHAIN-ORDER(p) 每个表项的复杂度是O （n ），共有O （n^2）表项，则为O （n^3） 1 n ← length[p] - 12 for i ← 1 to n3 do m[i, i] ← 04 for l ← 2 to n ▹l is the chain length.5 do for i ← 1 to n - l + 16 do j ← i + l - 17 m[i, j] ← ≦8 for k ← i to j - 19do q ← m[i, k] + m[k + 1, j] + pi-1 pkpj 10 if q < m[i, j]11 then m[i, j] ← q12 s[i, j] ← k13 return m and sPRINT-OPTIMAL-PARENS(s, i, j)1 if i = j2 then print "Ai "3 else print "("4 PRINT-OPTIMAL-PARENS(s, i, s[i, j])5 PRINT-OPTIMAL-PARENS(s, s[i, j] + 1, j)6 print ")"e ）备忘录算法：1）程序结构采用自顶向上；2）保留了递归结构，开销较大；3）当所有的子问题都需要求解时，自底向上的方法效率较高，否则可以采用备忘录方法。
备忘录算法的代码可以参照课本207页。
f ）最优二叉查找树：1）一棵最优二叉查找树不一定是一棵整体高度最小的树，也不一定总是把有最大概率的关键字放在根部来构造一棵最优二叉查找树。
5、贪心法（最优子结构性质+贪心选择性质）。
考点：学会证明最优子结构性质和贪心选择性质的问题。
a ）活动选择问题：⎪⎩⎪⎨⎧≠++==<<φφij jk i ij S if j k c k i c S if j i c }1],[],[{ 0],[max注意课本上224页地贪婪法定理证明，这就是贪婪法的合理性证明。
RECURSIVE-ACTIVITY-SELECTOR(s, f, i, j)1 m ← i + 12 while m < j and sm < fi ▹ Find the first activity in Sij.3 do m ← m + 14 if m < j5 then return {am} ∪RECURSIVE-ACTIVITY-SELECTOR(s, f, m, j)6 else returnGREEDY-ACTIVITY-SELECTOR(s, f)1 n ←length[s]2 A ←{a1}3 i ←1 24 for m ←2 to n5 do if sm ≥fi6 then A ←A ∪{am}7 i ←m8 return Ab）贪心算法遵循的步骤：1）决定问题的最优子结构；2）设计出一个递归解；3）证明在递归的任一阶段，最优选择之一总是贪心选择，那么，做贪心选择总是安全的；4）证明通过做贪心选择，所有的子问题（出一个以外）都为空；5）设计出一个实现贪心策略的递归算法；6）将递归算法转换成迭代算法。
c）根据贪心选择来构造最优子结构：1）将优化问题转化成这样一个问题，即先做出选择，再解决剩下的一个子问题；2）证明原问题总是有一个最优解是做贪心选择得到的，从而说明贪心选择的安全；3）说明在做贪心选择后，剩余的子问题具有这样的一个性质，即如果将子问题的最优解和我们所作的贪心选择联合起来，可以得出原问题的一个最优解。
d）贪心选择性质：证明定理16.1e）最优子结构性质：课本229页。
6、搜索（回溯法、剪枝函数、最小成本优先）。
考点：回溯，剪枝函数，最小成本优先的问题；分支界限法，剪枝函数所具备的性质。
a）回溯法：1）定义：回溯法(探索与回溯法)是一种选优搜索法，按选优条件向前搜索，以达到目标。
但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为―回溯点‖。
2）回溯法解题的步骤：a、针对所给的问题，定义问题的解空间；b、确定易于搜索的解空间结构；c、以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。
2）回溯法解决的n后问题：在一个n * n的棋盘上放臵n个王后，使得n后彼此不受攻击。
3）回溯法解决0-1背包问题：附：证明部分背包问题具有贪心选择性质。
课本练习题16.2-3：c剪枝函数：约束函数：剪去不满足约束函数的子树； 限界函数：剪去由限界函数表明不能得到最优解的子树。
n k x x x P x x x P k k <<⇒+0),...,,(),...,,(21121剪枝函数的必要条件：典型例题：1）求不等式的整数解 5x 1+4x 2-x 3<=10, 1<=x j <=3, i =1,2,32）装载问题：c）最小成本优先算法：注：分支——限界的基本思想：1回溯法的深度优先比较盲目2广度优先代价太高4能优先搜索那些最有希望得到解的路径6深入分析问题，得到有用的启发信息7利用启发信息构造成本函数8最小成本优先的搜索策略9结合剪枝函数典型题型：重拍九宫问题。