《算法导论》复习大纲

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

1、《算法设计与分析》复习提纲2014.7.51引言(ch1)1.什么是算法及其特征算法（Algorithm）是通过一个有限的指令序列集合对特定问题进行求解的一种计算执行描述。算法特征：（1）输入：一个算法具有零个或多个取自指定集合的输入值；（2）输出：对每一次输入，算法具有一个或多个与输入值相联系的输出值；（3）确定性：算法的每一个指令步骤都是明确的；（4）有限性：对每一次输入，算法都必须在有限步骤（即有限时间）内结束；（5）正确性：对每一次输入，算法应产生出正确的输出值；（6）通用性：算法的执行过程可用于所有同类求解问题，而不仅适用于特殊输入。2.问题实例和问题规模问题

2、实例是指需要计算同一个结果的问题的所有输入。问题规模是指输入实例的大小,而输入实例是指问题的具体计算例子2算法初步(ch2)1.插入排序算法1）算法步骤：从左到右扫描数据A，扫描到一个元素，将A[j]与其左边的元素从右到左依次比较，若比之小，则将其之前元素后移，插入A【j】,直至A【j】比他前面的元素大，扫描A中的下一个元素2）伪代码：InsertSort(A){forj=2toA.length//第一层循环｛Key=A[j]i=j-1Whilei>0anda[i]>key//第二层循环｛A[i+1]=A[i]｝i=i-1A[i+1]=key｝}2.算法复杂性及其度量(

3、1)时间复杂性和空间复杂性；(2)最坏、最好和平均情形复杂性；顺序情况下B（n）=O（n）、倒序情况下W（n）=O（n2）、A（n）=O(n2)

4、环进行上2步，直接所有元素都被合并到上级序列，公进行r-p+1次；2）伪代码：MERGE-SORT(A,p,r){ifp

5、定义及其使用1）O渐进上界：0<=f(n)<=C(g(n))当n->∞,f(n)的阶小与g(n)的阶2）Ω渐进下界：0<=C(g(n))<=f(n)当n->∞,f(n)的阶大与g(n)的阶3）Θ渐紧界：0<=C1(g(n))<=f(n)<=C2(g(n))当n->∞,f(n)的阶与g(n)的阶相等1.标准复杂性函数及其大小关系（1）多项式时间阶的大小O(1)证明2）对象限界最大最小项限界；几何级数限界；

6、3）和式分解简单的一分为二；更复杂的划分；积分近似；4）Knuth求和：使用数学归纳法；使用摄动法；使用递归；使用积分；使用二重求和；使用有限演算；使用母函数。4递归关系式(ch4)1.替换法(1)猜测解à数学归纳法证明；T（n）=2T(⌊n/2⌋)+n猜：T（n）=O(nlogn)证:2T(⌊n/2⌋)+n<=Cnlogn带入计算(2)变量变换法；T（n）=2T(⌊n1/2⌋)+logn令m=logn,则，n=2mT(2m)=2T(⌊2m-1/2⌋)+m，令S（m）=T(2m)则：S(m)=2S⌊m/2⌋+m类似T（n）=2T(⌊n/2⌋)+n=O(mlogm)=O(

7、lognloglogn)2.迭代法(1)展开法；T(1)=O(1)T（n）=3T(⌊n/4⌋)+n=n+3⌊n/4⌋+32⌊n/42⌋+…+3KT(n/4K)总有K，使得1==1,b>=1整数Case1f(n)=O(nlogba-Ɛ)<=Cnlogba-Ɛ则：T(n)=Θ（nlogba）Case2f(n)<=Θ(nlogba)则：T(n)=Θ（nlogba*logn）Ca