《算法复习呕心之作》由会员分享，可在线阅读，更多相关《算法复习呕心之作（20页珍藏版）》请在金锄头文库上搜索。
1、-1 引言(ch1)1. 什么是算法及其特征算法是通过一系列有限的指令集构成的对特定问题进展求解的计算机执行描述。算法特征：输入、输出、有限性、确定性、通用性2. 问题实例和问题规模问题实例：解决一个问题所需要的所有输入问题规模：算法输入实例的大小2 算法初步(ch2)1. 插入排序算法INSERT_SORT(A) for j-2 to lengthA Do key-Aj/将Aj插入到已排序的数列A1.j-1 i0 and Aikeydo Ai+1-Ai/给Aj腾出位置 i-i-1 Ai+1-key/找到位置插入key2.算法复杂性及其度量(1)时间复杂性和空间复杂性；一个算法所需要的时间通常
2、和输入的规模成同步增长，所以我们通常把算法运行的时间写成输入规模的*种形式，称为时间复杂度。算法的空间复杂度通常是指算法所需要的存存储空间的大小的量级，通常也写成输入规模的*种形式。(2)最坏、最好和平均情形复杂性；算法的最坏运行时间是指在任何输入情况下运行时间的一个上界。最好的复杂度是指在任何输入情况下运行时间的一个下界。平均时间复杂度是指算法运行时间的数学期望。3.插入排序的最坏、最好和平均时间插入排序的最坏时间复杂度是O(n2)发生在输入是逆序的情况下,最好时间复杂度是O(n)发生输入是顺序的情况下。平均时间复杂度同O(n2)。3. 归并排序算法及其时间复杂性MERGE(A,p,q,r)
3、/将两个排好序的数组合并n1-q-p+1n2-r-q/r-(q+1)+1create arrays L1.n1+1 and R1.n2+1/建立两个数组for i-1 to n1 do Li-Ap+i-1 for j-1 to n2 do Rj-Aq+j/A(q+1)+j-1 Ln1+1-ma*/Ma*表示无穷大 Ln2+1-ma*/用作哨兵i-1 j-1 for k-p to r do if Li=Rj then Ak-Li i-i+1 else Ak-Rj j-j+1MERGE-SORT(A,p,r)/归并排序采用分治发，分解+解决+合并if pr then qn0时有c1g(n)=f(n
4、)n0时有0=f(n)=cg(n)注：证明的时候找出n0和c即可，千万不要忘记还要证明0=n0的时候有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!)n0时候一切都符合猜想的结论)c.有时候得到T(n)=+1的时候需要在猜想解中减去一个低阶项，凑成T(n)=(2)变量变换法； 替换使式子变形为的熟悉的形式。如T(n)=2T(n/2)+n2.迭代法(1)展开法；关键是处理通项等于1的情况，也就是递归完毕的情况。(2)递
5、归树法；主要关注Runing time同一层上所有节点的时间和 和size原来的几分之几两个指标，选取size最慢到1的分支为标准分支最长的。3.主定理Case 3 的时候不要忘记证明af(b/n)=cf(n)对*个c1且足够大的n成立。5 概率分析(ch5)1.雇佣问题及其随机算法(略)2.序列随机排列的两种方法及其复杂性方法1：为每个Ai指定一个优先级pi然后按pi对A排序PermuteBySort()n-lengthA;for(i=1;i=n;i+)pi-Random(1n3);用p作为关键字对A 排序；Return A;时间复杂度：(nlogn)/主要用在排序上，归并排序的时间复杂度是
6、O(nlogn) 方法2：就地枚举 RandomInPlace(A)n-lengthA; for(i=1;i=n;i+) AiARandom(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)+2n
7、3.堆的操作：建堆；整堆；建堆操作是建立在整堆根底上的，整堆的原理是：假设i的以左孩子为根的子树和以右孩子为根的子树均为整好堆的大根堆，需要将i节点的值与left(i)和right(i)节点的值做比拟，如果i节点值最大则无需整堆已经是大顶堆,如果不是则找出左右孩子的最大值并交换i节点和子孩子节点的值，由于交换的过程中可能破坏了该子树的大顶堆的性质，则需要从该子节点开场继续整堆，是个递归的过程。MA*-HEAPIFY(A,i)l-left(i)r-right(i)if lAithen largest-lelse largest-iif rAlargestthen largest-rif lare
8、sti then do e*change AiAlargestMA*-HEAPIFY(A,largest)时间复杂度：O(logn)建堆：从lengthA/2处开场整堆，直至树根。BUILD-MA*-HEAPIFY(A)heap-sizeA-lengthAfor i-lengthA/2 downto 1do MA*-HEAPIFY(A,i)时间复杂度：O(n)/O(nlogn)为其非紧致界4.堆排序算法和时间复杂性堆排序算法的思想是：先交换、再整堆、再交换、在执行的过程中，始终保持该堆为大顶堆。HEAPSORT(A)BUILD-MA*-HEAP(A);/建堆O(n)for i-lengthA
9、downto 2/循环整堆+断裂O(nlogn)doe*change A1Ai heap-sizeA-heap-sizeA-1MA*-HEAPIFY(A,1)时间复杂度为：O(n+nlogn)5.优先队列及其维护操作(1)插入操作MA*-HEAP-INSERT(A,key) heap-sizeA+;i1 and Ai.parentkey) do Ai-Aparenti;i-parenti;Ai-key;时间复杂度为O(logn) (2)取最大关键字Return A1;/时间O(1) (3)删除堆顶元素出队HEAP-E*TRACT-MA*(A)if heap-sizeA1 then return
10、 “Over Flow; MA*-A1; A1Aheap-sizeA;heap-sizeA-; MA*-HEAPIFY(A,1)/O(logn)/显然时间复杂度为O(logn)(4)增值HEAP-INCRESE-KEY(A,i,key)/将Ai增至key if(Ai=key)/往下调整 then Ai1 and Aparentikey) doAi-Aparentii-parenti Ai-key时间复杂度为O(logn)总结：所有的优先队列的维护操作均可以在O(logn)时间完成。7 快速排序(ch7)1. 快速排序算法及其最好、最坏时间和平均时间快速排序采用分治法，把问题分为更小的规模，每次划分都调用一个算法生成一个划分源q将数组Ap.r分成Ap.q-1 、Aq、Aq+1.r三局部QuickSort(A,p,r)/对Ap.r快排序if(pr) then/递归到p=r时完毕q-Partition(A,p,r);/生成划分源QuickSort(A,p,q-1);/子问题1QuickSort(A,q+1,r);/子问题2Partition(A,p,r)/划分源生成算法1，选取Ar为划分源，使其左边元素小于它，右边元素大于它*-Ar;i-p-1;for(j=p;j=r-1;j+)/始终保持Ap.i中的元素小于Arif(*Ar)i-i+1;AiAj;Ai+1
