算法复习整理呕心之作

《算法复习整理呕心之作》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、.《算法设计与分析》复习提纲2011.06.121引言(ch1)1.什么是算法及其特征算法是通过一系列有限的指令集构成的对特定问题进行求解的计算机执行描述。算法特征：输入、输出、有限性、确定性、通用性2.问题实例和问题规模问题实例：解决一个问题所需要的所有输入问题规模：算法输入实例的大小2算法初步(ch2)1.插入排序算法INSERT_SORT(A)forj<-2tolength[A]Dokey<-A[j]//将A[j]插入到已排序的数列A[1..j-1]i<-j-1whilei>0andA[i]>keydoA[i+1]<-A[i]//给A[j]腾出位置i<-i-1A[i+1]<

2、-key//找到位置插入key2.算法复杂性及其度量(1)时间复杂性和空间复杂性；一个算法所需要的时间通常和输入的规模成同步增长，所以我们通常把算法运行的时间写成输入规模的某种形式，称为时间复杂度。算法的空间复杂度通常是指算法所需要的内存存储空间的大小的量级，通常也写成输入规模的某种形式。(2)最坏、最好和平均情形复杂性；算法的最坏运行时间是指在任何输入情况下运行时间的一个上界。最好的复杂度是指在任何输入情况下运行时间的一个下界。平均时间复杂度是指算法运行时间的数学期望。3.插入排序的最坏、最好和平均时间插入排序的最坏时间复杂度是O(n2)发生在输入是逆序的情况下,最好时间复杂度

3、是O(n)发生输入是顺序的情况下。平均时间复杂度同O(n2)。3.归并排序算法及其时间复杂性MERGE(A,p,q,r)//将两个排好序的数组合并n1<-q-p+1n2<-r-q//r-(q+1)+1...createarraysL[1..n1+1]andR[1..n2+1]//建立两个数组fori<-1ton1doL[i]<-A[p+i-1]forj<-1ton2doR[j]<-A[q+j]//A[(q+1)+j-1]L[n1+1]<-max//Max表示无穷大L[n2+1]<-max//用作哨兵i<-1j<-1fork<-ptordoifL[i]<=R[j]thenA[k]<

4、-L[i]i<-i+1elseA[k]<-R[j]j<-j+1MERGE-SORT(A,p,r)//归并排序采用分治发，分解+解决+合并ifpn0时有c1g(n)=n0时有0

5、=n0的时候有f(n)>=cg(n)成立（（注：证明的时候找出符合条件的n0和c即可）2.标准复杂性函数及其大小关系(1)多项式时间阶的大小O(1)

6、两项比值小于1进行几何级数的限界。(3)和式分解a.简单的分解b.忽略和式初始几项...a.更复杂的划分，要充分考虑和式的规律性b.积分近似（分为f(k)单调递增和递减两种情况）可用于求紧致界c.Knuth求和的七种方法4递归关系式(ch4)1.替换法(1)猜测解à数学归纳法证明；注：a.出现T(n/2)的情况下要假设T(n/2)符合条件，继而得到T(n)符合条件b.不要忘记证明归纳基础(n=1、n=2直到找到一个n0，使得对n>n0时候一切都符合猜测的结论)c.有时候得到T(n)<=cn+1的时候需要在猜测解中减去一个低阶项，凑成T(n)<=cn(2)变量变换法；替换使式子变形

7、为已知的熟悉的形式。如T(n)=2T(n/2)+n2.迭代法(1)展开法；关键是处理通项等于1的情况，也就是递归结束的情况。(2)递归树法；主要关注Runingtime（同一层上所有节点的时间和）和size（原来的几分之几）两个指标，选取size最慢到1的分支为标准（分支最长的）。3.主定理Case3的时候不要忘记证明af(b/n)<=cf(n)对某个c<1且足够大的n成立。5概率分析(ch5)1.雇佣问题及其随机算法(略)2.序列随机排列的两种方法及其复杂性方法1：为每个A[i