算法导论复习资料

《算法导论复习资料》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、算法导论复习资料一、选择题：第一章的概念、术语。二、考点分析：1、复杂度的渐进表示，复杂度分析。2、正确性证明。考点：1)正确性分析(冒泡，归并，选择)；2)复杂度分析(渐进表示O,Q,©,替换法证明，先猜想，然后给出递归方程)。循环不变性的三个性质：1)初始化：它在循环的第一轮迭代开始之前，应该是正确的；2)保持：如果在循环的某一次迭代开始之前它是正确的，那么，在下一次迭代开始之前，它也应该保持正确；3)当循环结束时，不变式给了我们一个有用的性质，它有助于表明算法是正确的。插入排序算法：INSERTION-SORT(A)1forj<-2tolen

2、gth[A]2dokey<-A[j]3>InsertA[j]intothesortedsequenceA[1,j-1].4i<-j-15whilei>0andA[i]>key6doA[i+1]<-A[i]7i<-i-18A[i+1]<-key插入排序的正确性证明：课本11页。归并排序算法：课本17页及19页。归并排序的正确性分析：课本20页。3、分治法(基本步骤，复杂度分析)。一一许多问题都可以递归求解考点：快速排序，归并排序，渐进排序，例如：12球里面有一个坏球，怎样用最少的次数找出來。(解：共有24种状态，至少称重3次可以找出不同的球)不是考点

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的元素。Givea0(nlgn)

4、timealgorithmfordeterminingifthereexisttwoelementsinansetSwhosesumisexactlysomevaluex.Algorithm4CheckSums(A.x)Input:AnanayAandavaluex.Output:AbooleanvalueindicatingifthereistwoelementsinAwhosesumisx.A<—SORT(A)n<—/engt/i[A]foritottdoifA[i]>0andBinary・Search(A,A

5、i]一xj.n)thenretu

6、rntrueendifendforreturnfalseClearlythisalgorithmdoesthejob.(Itisassumedthatnilcannotbetmeintheif-statement.)1+?+3+4+5+6+7+8+9+1()+11+12+1~2-3~4~5-6-7—8-9~1(厂11-12-1+2+3+4+5—6_7-8-9+1()+11+12-旷lo-ir12-3+4+6-1一2一5+1+2+5-6+3一4一7+8+1叵RMRREEEHMMMElEIRMRrzlMlsR回一3EMSH4动态规划（最优子结构性质，自

7、底向上填表计算最优解值（即最长公共子序列），导出最优解考点：最优了结构性质，自底向上填表计算最优解值，导岀最优解。a）动态规划算法设计的4个步骤：1）描述最优解的结构；2）递归定义最优解的值；3）按自底向上的方式计算最优解的值；4）由计算出的结果构造一个最优解。b）最优子结构遵循的共同模式：1）问题的一个解可以是做一个选择，做这种选择可能会得到一个或多个有待解决的子问题；2）假设对一个给定的问题，已知的是一个可以导致最优解的选择，不必关心如何确定这个选择，尽管假定它是已知的；3）在已知这个选择后，要确定哪些子问题会随之发生，以及如何最好地描述所得到

8、的子问题的空间；4）利用一种“剪切粘贴法“,来证明在问题的一个最优解中，使用的子问题的解本身也必须是最优的。备注Aproblemexhibitsoptimalsubstructureifanoptimalsolutiontotheproblemcontainswithinitoptimalsolutionstosubproblems.Wheneveraproblemexhibitsoptimalsubstuctureitisagoodcluethatdynamicprogrammingmightapply.c)最长公共子序列的算法：这里以两个序列X

9、二｛x1,x2，…,xm｝和Y二｛屮旳…如｝为输入，注意课本211页的自底向上填表方法。LCS-LENGTH(X,Y)注：