算法复习整理(呕心之作)

《算法设计与分析》复习提纲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-1whilei0andA[i]keydoA[i+1]-A[i]//给A[j]腾出位置i-i-1A[i+1]-key//找到位置插入key2.算法复杂性及其度量(1)时间复杂性和空间复杂性；一个算法所需要的时间通常和输入的规模成同步增长，所以我们通常把算法运行的时间写成输入规模的某种形式，称为时间复杂度。算法的空间复杂度通常是指算法所需要的内存存储空间的大小的量级，通常也写成输入规模的某种形式。(2)最坏、最好和平均情形复杂性；算法的最坏运行时间是指在任何输入情况下运行时间的一个上界。最好的复杂度是指在任何输入情况下运行时间的一个下界。平均时间复杂度是指算法运行时间的数学期望。3.插入排序的最坏、最好和平均时间插入排序的最坏时间复杂度是O(n2)发生在输入是逆序的情况下,最好时间复杂度是O(n)发生输入是顺序的情况下。平均时间复杂度同O(n2)。3.归并排序算法及其时间复杂性MERGE(A,p,q,r)//将两个排好序的数组合并n1-q-p+1n2-r-q//r-(q+1)+1createarraysL[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]-L[i]i-i+1elseA[k]-R[j]j-j+1MERGE-SORT(A,p,r)//归并排序采用分治发，分解+解决+合并ifprthenq-(p+r)/2//下取整，分解MERGE-SORT(A,p,q)//解决一半MERGE-SORT(A,q+1,r)//解决另一半MERGE(A,p,q,r)//合并时间复杂度为O(nlogn)3函数增长率(ch3)1.渐近记号O、Ω、θ的定义及其使用θ:渐紧界，即存在n0,c1,c2,当nn0时有c1g(n)=f(n)=c2g(n)（注：证明的时候找出n0,c1,c2即可）O:渐进上界，即存在n0,c当nn0时有0=f(n)=cg(n)（注：证明的时候找出n0和c即可，千万不要忘记还要证明0=f(n)的情况，会影响n0的取值）Ω：渐进下界，即存在n0,c,当nn0的时候有f(n)=cg(n)成立（（注：证明的时候找出符合条件的n0和c即可）2.标准复杂性函数及其大小关系(1)多项式时间阶的大小O(1)O(logn)O(n)O(nlogn)O(n2)O(n3)……(2)指数时间阶的大小O(2n)O(n!)O(nn)3.和式界的证明方法(1)数学归纳法，先猜，后用数学归纳法按照界的证明方法证明（求c和n0）(2)对项进行限界：利用最大、最小值进行放缩，以及利用和式的前后两项比值小于1进行几何级数的限界。(3)和式分解a.简单的分解b.忽略和式初始几项c.更复杂的划分，要充分考虑和式的规律性d.积分近似（分为f(k)单调递增和递减两种情况）可用于求紧致界e.Knuth求和的七种方法4递归关系式(ch4)1.替换法(1)猜测解数学归纳法证明；注：a.出现T(n/2)的情况下要假设T(n/2)符合条件，继而得到T(n)符合条件b.不要忘记证明归纳基础(n=1、n=2直到找到一个n0，使得对nn0时候一切都符合猜测的结论)c.有时候得到T(n)=cn+1的时候需要在猜测解中减去一个低阶项，凑成T(n)=cn(2)变量变换法；替换使式子变形为已知的熟悉的形式。如T(n)=2T(n/2)+n2.迭代法(1)展开法；关键是处理通项等于1的情况，也就是递归结束的情况。(2)递归树法；主要关注Runingtime（同一层上所有节点的时间和）和size（原来的几分之几）两个指标，选取size最慢到1的分支为标准（分支最长的）。3.主定理Case3的时候不要忘记证明af(b/n)=cf(n)对某个c1且足够大的n成立。5概率分析(ch5)1.雇佣问题及其随机算法(略)2.序列随机排列的两种方法及其复杂性方法1：为每个A[i]指定一个优先级p[i]然后按p[i]对A排序PermuteBySort(){n-length[A];for(i=1;i=n;i++)p[i]-Random(1~n3);用p作为关键字对A排序；ReturnA;}时间复杂度：θ(nlogn)//主要用在排序上，归并排序的时间复杂度是O(nlogn)方法2：就地枚举RandomInPlace(A){n-length[A];for(i=1;i=n;i++)A[i]-A[Random(1,n)];//直接就地生成优先级后就交换位置}时间复杂度：θ(n)3.online雇佣问题及其概率分析(略)6堆排序(ch6)1堆的概念和存储结构堆是一种数据结构它是一种数组对象，可以视为一棵完全二叉树。每一层都是满的，最后一层可能除外。2.堆的性质和种类(1)子节点和父节点下标之间的关系某节点的下标是i，则left(i)=2i,right(i)=2i+1Parent(i)=(i/2)的下取整。(2)n个节点的堆其叶子节点为(n/2)+1,(n/2)+2……n3.堆的操作：建堆；整堆；建堆操作是建立在整堆基础上的，整堆的原理是：假设i的以左孩子为根的子树和以右孩子为根的子树均为整好堆的大根堆，需要将i节点的值与left(i)和right(i)节点的值做比较，如果i节点值最大则无需整堆已经是大顶堆,如果不是则找出左右孩子的最大值并交换i节点和子孩子节点的值，由于交换的过程中可能破坏了该子树的大顶堆的性质，则需要从该子节点开始继续整堆，是个递归的过程。MAX-HEAPIFY(A,i){l-left(i)r-right(i)ifl=heap-size[A]andA[l]A[i]thenlargest-lelselargest-iifr=heap-size[A]andA[r]A[largest]thenlargest-riflarest≠ithendoexchangeA[i]-A[largest]MAX-HEAPIFY(A,largest)}时间复杂度：O(logn)建堆：从length[A]/2处开始整堆，直至树根。BUILD-MAX-HEAPIFY(A)heap-size[A]-length[A]fori-length[A]/2downto1doMAX-HEAPIFY(A,i)时间复杂度：O(n)//O(nlogn)为其非紧致界4.堆排序算法和时间复杂性堆排序算法的思想是：先交换、再整堆、再交换、在执行的过程中，始终保持该堆为大顶堆。HEAPSORT(A)BUILD-MAX-HEAP(A);//建堆O(n)fori-length[A]downto2//循环整堆+断裂O(nlogn)doexchangeA[1]-A[i]heap-size[A]-heap-size[A]-1MAX-HEAPIFY(A,1)时间复杂度为：O(n+nlogn)5.优先队列及其维护操作(1)插入操作MAX-HEAP-INSERT(A,key){heap-size[A]++;i-heap-size[A];while(i1andA[i].parentkey)do{A[i]-A[parent[i]];i-parent[i];}A[i]-key;}时间复杂度为O(logn)(2)取最大关键字ReturnA[1];//时间O(1)(3)删除堆顶元素（出队）HEAP-EXTRACT-MAX(A){ifheap-size[A]1thenreturn“OverFlow”;MAX-A[1];A[1]-A[heap-size[A]];heap-size[A]--;MAX-HEAPIFY(A,1)//O(logn)}//显然时间复杂度为O(logn)(4)增值HEAP-INCRESE-KEY(A,i,key){//将A[i]增至keyif(A[i]=key)//往下调整thenA[i]-keyMAX-HEAPIFY(A,i)else//往上调整while(i1andA[parent[i]]key)doA[i]-A[parent[i]]i-parent[i]A[i]-key}时间复杂度为O(logn)总结：所有的优先队列的维护操作均可以在O(logn)时间内完成。7快速排序(ch7)1.快速排序算法及其最好、最坏时间和平均时间快速排序采用分治法，把问题分为更小的规模，每次划分都调用一个算法生成一个划分源q将数组A[p..r]分成A[p..q-1]、A[q]、A[q+1..r]三部分QuickSort(A,p,r){//对A[p..r]快排序if(pr)then//递归到p=r时结束{q-Partition(A,p,r);//生成划分源QuickSort(A,p,q-1);//子问题1QuickSort(A,q+1,r);//子问题2}}Partition(A,p,r)//划分源生成算法1，选取A[r]为划分源，使其左边元素小于它，右边元素大于它{x-A[r];i-p-1;for(j=p;j=r-1;j++){//始终保持A[p..i]中的元素小于A[r]if(xA[r]){i-i+1;A[i]-A[j];}}A[i+1]-A[r];//A[r]就位returni+1;//返回q}快速排序实际上是一个就地（Inplace）排序。性能分析：（1）最坏的划分：A[p..q-1],A[q+1,r]有一个是空的T(n)=T(n-1)+T(0)+θ(n)//数组最后一个元素是最大的情况（做为划分源），前面是n-1个元素，后面元素个数为0。θ(n)为生成划分源的时间。由迭代法：T(n)=θ(n2)（2）最好的划分：比较平均，两部分一样大T(n)=2T(n/2)+θ(n)//一个大小为n/2,另一个为n/2-1,规模小于2T(n/2)由master定理的case2可知T(n)=O(nlogn)(3)平衡的划分，每次划分保持固定比例，其运行时间接近最好的划分为O(nlogn)，只要按照固定比例划分，得到的时间复杂度都是O(nlogn)2.随机快速排序算法及其期望时间随机快速排序要求每次的划分源随机产生只需改动partition为RandomizedPartion(A,p,r){j-Random(p,r);//随机在A[p..r]中选择元素作为划分源A[r]-A[i];//将A[i]交换到最后，因为partition是以最后元素作为划分源的ReturnParition(A,p,r);//返回划分源q}期望时间为1.44nlogn(knuth时间分析)，为O(nlogn)。8线性时间排序(ch8)1.基于比较的排序算法下界：Ω(nlogn)可以用判定树进行说明。2.计数排序适应的排序对象、算法和时间适应的排序对象：一列有相同元素或没有相同元素的整数数列。元素互不相同时的算法：SpecialCountingSort(A,B){//B[1..n]为排序结果fori←1tondoB[A[i]]←A[i];//如A[i]=5，就放到B[5]中，小于5的元素不超过5个。}时间：O(n)，无比较，当数组不是连续的整数时比较浪费空间。有相同元素时的算法：