1、算法设计与分析复习提纲 2014.7.51 引言(ch1)1. 什么是算法及其特征算法（Algorithm）是通过一个有限的指令序列集合对特定问题进行求解的一种计算执行描述。算法特征：（1）输入：一个算法具有零个或多个取自指定集合的输入值；（2）输出：对每一次输入，算法具有一个或多个与输入值相联系的输出值；（3）确定性：算法的每一个指令步骤都是明确的；（4）有限性：对每一次输入，算法都必须在有限步骤（即有限时间）内结束；（5）正确性：对每一次输入，算法应产生出正确的输出值；（6）通用性：算法的执行过程可用于所有同类求解问题，而不仅适用于特殊输入。2.问题实例和问题规模问题实例是指需要计算同一个
2、结果的问题的所有输入。问题规模是指输入实例的大小,而输入实例是指问题的具体计算例子2 算法初步(ch2)1. 插入排序算法1）算法步骤：从左到右扫描数据A，扫描到一个元素，将Aj与其左边的元素从右到左依次比较，若比之小，则将其之前元素后移，插入A【j】,直至A【j】比他前面的元素大，扫描A中的下一个元素2）伪代码：InsertSort(A)for j=2 to A.length /第一层循环Key=Aji=j-1While i0 and aikey /第二层循环Ai+1=Aii=i-1Ai+1=key 2.算法复杂性及其度量 (1)时间复杂性和空间复杂性； (2)最坏、最好和平均情形复杂性；顺
3、序情况下B（n）=O（n）、倒序情况下W（n）=O（n2）、A（n）=O(n2)W(n)空间复杂性：需要常数个额外的临时空间存储临时数据2. 插入排序的最坏、最好和平均时间最坏O(n2)、最好O(n)和平均时间O(n2),空间复杂度是O(1)，稳定排序3. 归并排序算法及其时间复杂性时间（n log n）1）算法步骤分解：分解待排序的n个元素的序列为各具n/2个元素的两个子序列解决：适用归并排序递归的排序2个子序列合并：从左到有遍历2个子序列，比较最前面的元素，将较小的元素移出子序列 合并到上级序列的末尾，循环进行上2步，直接所有元素都被合并到上级序列，公进行r-p+1次；2）伪代码：MERG
4、E-SORT(A,p,r) if prq=向下取整（p+r）/2MERGE-SORT(A,p,q);MERGE-SORT(A,q+1,r)MERGE(A,p,q,r)MERGE(A,p,q,r)N1=q-p+1N2=r-q将A拆成长度分别为N1、n2的2个子数组L,RL,R的末尾元素的后一个元素取值无穷大，作为哨兵；i=1，j=1for k=p to r if Li=RjAk=Lii=i+1elseAk=Rjj=j+1 3函数增长率(ch3)1. 渐近记号O、的定义及其使用1） O渐进上界：0=f(n), f(n)的阶小与g(n)的阶2）渐进下界：0=C(g(n) , f(n)的阶大与g(n)
5、的阶3）渐紧界：0=C1(g(n) =f(n) , f(n)的阶与g(n)的阶相等2. 标准复杂性函数及其大小关系（1） 多项式时间阶的大小O(1) O(log n) O(n) O(n*log n) O(n) O(n3)（2） 指数时间阶的大小O(2n) O(n!) 证明2）对象限界最大最小项限界；几何级数限界；3）和式分解简单的一分为二；更复杂的划分；积分近似；4）Knuth求和：使用数学归纳法；使用摄动法；使用递归；使用积分；使用二重求和；使用有限演算；使用母函数。4 递归关系式(ch4)1.替换法(1)猜测解数学归纳法证明；T（n）=2T(n/2)+n 猜：T（n）= O(nlogn)证
6、: 2T(n/2)+n=Cnlogn 带入计算(2)变量变换法；T（n）=2T(n1/2)+log n令m= logn,则，n=2mT(2m)=2T(2m -1/2)+m ，令S（m）=T(2m)则：S(m)=2Sm/2+m类似T（n）=2T(n/2)+n=O(m log m)=O(logn log log n)2.迭代法(1)展开法；T(1)=O(1)T（n）=3T(n/4)+n=n+3n/4+32n/42+3KT(n/4K)总有K，使得1=n/4K=2,即K=1,b=1整数Case1 f(n)= O(n logba-) = C n logba- 则：T(n)= （n log b a）Cas
7、e2 f(n)= C n logba+ 且：af(n/b)=cf(n),对于常数C=1和足够大的n成立，则T(n)= （f(n)）5 堆排序(ch6)1堆的概念和存储结构堆是一种数据结构，堆是一个数组，近似完全二叉树，除最底层外，全部从左到右填充满，对于序号为i的结点，其父结点的序号为i/2,其左孩子的序号为2i,其右孩子序号为2i+1;0=A.heap-size=A.length n个元素的序列k1,k2,ki,kn当且仅当满足下关系时，称之为堆。(ki= k2i,ki= k2i,ki= k2i+1), (i = 1,2,3,4.n/2)l 堆的性质和种类大根堆：除根结点外，所有结点小于其父
8、结点；用于堆排序、收益问题。小根堆：除根结点外，父结点小于其所有结点；用于优先队列；成本问题；l 堆的操作：建堆；整堆；1)整堆算法：假设i的左右子树已经是大根堆,对i结点进行整堆，使其也是大根堆对调整的子树结点循环进行上2步骤，将小元素逐级下沉，直至满足堆特性；整堆时间复杂度 O（log n）2)整堆伪代码Max-heapify(A,i) l=left(i)r=right(i)if lAilargest=lelse largest=iif rAilargest=rif largestiexchange ai with largestmax-heapify(A,largest)3)建堆算法因为
9、从A.heap-size/2+1起到A.heapsize，都是叶子结点，故建堆可从A.heap-size/2起到1整堆实现；算法复杂度O（n）4)建堆伪代码Bulid_max_heap(A)heap-size=A.lengthfor i= A.heap-size /2 to 1Max-heapify(A,i)l 堆排序算法和时间复杂性算法思想：1）将数组建堆2）将根元素与结点n交换并缩减堆的长度13）对首元素整堆4）重复上述3个步骤，直至堆大小为1（i=2时进行最后一次重复操作）时间复杂度O（n lg n）伪代码Heapsize(A) build_max_heap(A) For i=A.len
10、gth to 2 Exchange A1 to Ai A.heap-size=A.heap-size-1 max-heapfly(A,1)l 优先队列及其维护操作优先队列是维护集合S的数据结构，每个元素具有一个关键字key；用于分支限界、搜索算法。支持如下操作：a) 插入 insert(S,x) 算法思想：1）将元素插入末尾Size+1的位置2）从插入位置自底而上调整，使之满足堆性质算法复杂度 O（log n）b) 取最大关键字Maximum(S)算法思想，输出优先级最大的，也就是堆的根元素；c)删除并返回最大键值的元素 Extract-max(S)算法思想：1） 取堆根2） A1-Aheap
11、-sizeA3） heap-sizeA4） 对A1整堆时间复杂度O（log n）d) 增值 元素x的关键字增加到k Increase-Key(S,x,k)算法思想：1）如果Ai的关键字大于K，则对i进行整堆；2）否则，若i不是根结点且K大于Ai的父结点，则交换Ai与其父结点的关键字，并将K值赋予其父结点。时间复杂度O（log n）6 快速排序(ch7)1. 快速排序算法及其最好、最坏时间和平均时间快排采用分治法的思想，最好O(nlogn),最坏O(n2),平均O(nlogn)（1）分治法的基本思想 分治法的基本思想是：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，
12、然后将这些子问题的解组合为原问题的解。（2）快速排序的基本思想 设当前待排序的无序区为Rlow.high，利用分治法可将快速排序的基本思想描述为：分解： 在Rlow.high中任选一个记录作为基准(Pivot)，以此基准将当前无序区划分为左、右两个较小的子区间Rlow.pivotpos-1)和Rpivotpos+1.high，并使左边子区间中所有记录的关键字均小于等于基准记录(不妨记为pivot)的关键字pivot.key，右边的子区间中所有记录的关键字均大于等于pivot.key，而基准记录pivot则位于正确的位置(pivotpos)上，它无须参加后续的排序。Ap.r被划分为俩个（可能空）
13、的子数组Ap .q-1和Aq+1 .r，使得Ap .q-1 = Aq = Aq+1 .r求解：通过递归调用快速排序对左、右子区间Rlow.pivotpos-1和Rpivotpos+1.high快速排序。3合并/快速排序void quick_sort(int s, int l, int r) if (l r) int i = l, j = r, x = sl; while (i j) while(i = x) / 从右向左找第一个小于x的数 j-; if(i j) si+ = sj; while(i j & si x) / 从左向右找第一个大于等于x的数 i+; if(i j) sj- = si
14、; si = x; quick_sort(s, l, i - 1); / 递归调用 quick_sort(s, i + 1, r); 2.随机快速排序算法及其期望时间期望时间负责度O(nlogn)算法描述：分解：以ap为基准元素将ap:r划分为3段ap:q-1,aq和aq+1:r,使 ap:q-1中任何一个元素小于等于aq，而aq+1:r中任何一个元素大于等于aq。下标q在划分过程中确定。递归求解：通过递归调用快速排序算法分别对ap:q-1和aq+1:r进行排序。合并：由于对ap:q-1和aq+1:r的排序是就地进行的，所以在ap:q-1和aq+1:r都已排好的序后，不需要执行任何计算，ap:
15、r就已排好void RandomizedQuickSort(double *a,int begin,int end) /随机化快速排序 if(beginend) int p = RandomizedPartition(a,begin,end); RandomizedQuickSort(a,begin,p-1); RandomizedQuickSort(a,p+1,end); intRandomizedPartition(double*a,intbegin,intend) inti=Random(begin,end);doubletemp=aend;aend=ai;ai=temp; return
16、Partition(a,begin,end);int Random（int m,int n） /产生一个随机下表，用其对应的数组元素作为比较标准srand(unsigned)time(NULL);return m+(rand()%(n-m+1);int Partition(double *a,intbegin,int end) int i = begin-1,j=begin; double x = aend; while(jend) if(ajB小于或等于Ai的元素数目主要要解决的问题： 计数：统计小于或等于 统计小于或等于Ai的元素数目 值相同元素的处理一种特殊情形的计数排序：问题：n个互不
17、相同的整数A1.n，1Ain，i=1n排序算法：SpecialCountingSort(A,B)/B1.n为排序结果for i1 to n do BAiAi; /如Ai=5，就放到B5中时间：O(n) ，无比较一般情形的计数排序：问题：n个可以相同的整数A1.n，1Aik，i=1n，这里k是Ai的取值范围，不一定为n。基本思想：步骤：A1.n计数器C1.kB1.n Step 1(值相同元素的计数 值相同元素的计数)：将A中的值为i的元素个数记入Ci中； Step 2(累计计数)：对C1.k进行修改，使得Ci的值表示为i的元素个数； Step 3(放置)：将Aj依据C Aj，放入正确位置BCAj
18、上，并修改CAj CAj-1；算法：CountingSort(A,B,k)/ B1.n为排序结果，C1.k为计数数组for i1 to k do Ci0;for j1 to lengthA do / 扫描A，值相同元素计数 值相同元素计数CAj+; for i2 to k do / Ci修改，累计计数CiCi+Ci-1; for jlengthA downto 1 do BCAjAj; CAj-; 时间：T(n k)=(n+k)=(n) 如果k=(n)时3. 基数排序适应的排序对象、算法和时间假定A1.n是非负整数，用k进制表示为不超过d位数。l算法：RadixSort(A d) RadixS
19、ort(A,d) for i1 to d do使用稳定的排序算法对 使用稳定的排序算法对A的第i位排序；/如计数排序l时间：T(n)=(d(n+k) /k为基，d为位数=(n) /如果k=(n)且d是常数示例：引理8.3, 给定n个d位数，其中每一个数位有k个可能的取值。如果RADIX-SORT使用的稳定排序方法耗时(n+k)，那么它就可以在(d(n+k)时间内将这些数排好序。证明：当每位数字都在0到k-1区间内（这样它就有k个可能的取值），且k的值不太大的时候，计数排序是一个好的选择。对n个d位数来说，每一轮排序耗时(n+k)。共有d轮，因此基数排序的总时间为(d(n+k).d不为常数，基数
20、排序算法还是线性时间吗？设n个整数的取值范围是0nc，c是整常数，c1对于十进制整数，nc需要的位数d=log10nc+1log10nT(n)=(d(n+k) =(nlogn) /k为10因此，不是线性时间排序l算法何时为线性时间？Idea: 只要使d变为常数，k变大到与n同阶How to do How to do : 选基k=n，则nc的位数为lognnc=c=dd=c， k=nT(n)=(n)4. 桶排序适应的排序对象、算法和时间假定：输入是均匀分布在0,1)上的实数。l基本思想：0,1)划分为0,1/n),1/n,2/n),k/n,(k+1)/n),(n-1)/n,1)n个大小相等的子区
21、间，每个子区间看作一个桶；将n个元分配桶中；对每个桶里的元素进行排序，依次连接桶；输入：0A1.n1l辅助数组：B0.n-1是一个指针数组，指向每个桶(链表)l关键字映射：由于0Ai 1，必须将Ai映射到0, 1n-1上0,1)0,n) /通过函数nAi即knA ik+1 /存在k桶号k=nAi/映射函数算法描述：BucketSort( A)nlengthA; Timefor i1 to n do /扫描A (n)将Ai插入到链表BnAi中;for i0 to n-1 do (n)*用插入排序将Bi排序;将B0, B1, Bn-1连接起来;(n)注：n个数是均匀分布在0 1)中，每个桶中大约只
22、有一个数，时间为O(1)8 中位数和顺序统计(ch9)1. 最大和最小值的求解方法最小/最大值：最坏情形W(n)=n-1次比较，时间为(n)l同时求最大、最小值 一种方法：独立分别求，比较次数为n-1+n-2=2n-3 另一种方法：成对输入x, y，每对比较3次比较x, y；将min(x, y)与当前最小值比较；将max(x, y)与当前最大值比较；总比较次数约为3n/2。/第一对元素比较一次，最后一组元素若为一个，至多比较二次2. 期望时间为线性的选择算法基于分治法的思想：利用快排序的随机划分法，进行问题的划分具体步骤： 划分Ap.r = Ap.q-1AqAq+1.r； /Aq为划分元 K
23、- q-p+1; /即Aq是第k个最小元 If (i=k) then / k=左区间长度+1return Aq；If(ik) then 在右区间中继续找第i-k个元素； 临界条件：当区间长度为1时，直接返回该元素RandomizedSelect(A, p, r, i) /选择ith元素if p=r then return Ap; /临界问题处理qRandomizedPartition(A, p, r); /进行划分并返回划分元的下标kq-p+1; /Aq是第k个小的元素if i=k then/Aq是ith元素return Aq;else if ik then/ith元素落在左区间return
24、RandomizedSelect(A, p, q-1, i);else/ith元素落在右区间return RandomizedSelect(A, q+1, r, i-k);最好：每次划分为相等的左右区间 T(n)=T(n/2)+n = T(n)=(n)最坏：每次划分为不均等的左右区间T(n)=T(n-1)+n = T(n)=(n2)平均(期望)：分析略。T(n)=(n)3. 最坏时间为线性的选择算法及其时间分析算法步骤：While n1 dostep 1.将n个元素分成5个1组，共n/5组。其中最后1组有n mod 5个元素。step 2.用插入排序对每组排序，取其中值。若最后1组有偶数个元素
25、，取较小的中值。step 3 .递归地使用本算法找找n/5个中值的中值x。step 4.用x作为划分元对A数组进行划分，并设x是第k个最小元。step 5. if i=k then return x;else if i 左区间和右区间的最大长度7n/10+6运行时间递归式的建立step 1 2: O(1); step 3: T(n/5);step 4: O(n);step 5: 至多T(7n/10+6)(n/5向上取整)运行时间递归式的求解用替代法证：T( )n) cnT(n)c n/5+c(7n/10+6)+an /a为常数c(n/5+1)+c(7n/10+6)+an= cn/5+c+7cn
26、/10+6c+an= 9cn/10+7c+an= cn+(-cn/10+7c+an) cn/if -cn/10+7c+an0要使-cn/10+7c+an0，只要c10an/(n-70)假定n140， 有n/(n-70)2取c20a =-cn/10+7c+an0故T(n)=O(n)9 红黑树(ch13)1. 红黑树的定义和节点结构Def. 1: 红黑树是满足下述性质的二叉搜索树每个节点必须为红色或黑色 每个节点必须为红色或黑色； /性质1根为黑色；/性质2树中的nil叶子为黑； /性质3若节点为红，则其两个孩子必为黑；/性质4每节点到其后代叶子的所有路径含有同样多的黑节点；/性质5节点的结构Pa
27、rentleftCorlorKeyRight2. 黑高概念Def. 2：节点x的黑高bh(x)是该节点到它的任何后代叶子路径上的黑节点数(不包括x本身)Def. 3：红黑树的黑高是根的黑高，记bh(rootT)3. 一棵n个内点的红黑树的高度至多是2log(n+1)先证对任何以x为根的子树其内节点数2bh(x)-1归纳基础：当bh(x)=0时，x就是nilT 2bh(x)-1= 20-1=0 即为0个内节点，正确归纳假设：对x的左右孩子命题正确归纳证明：x的左右孩子的黑高或为bh(x)或为bh(x)-1x的内点数=左孩子内点数+右孩子内点数+1(2bh(x)-1-1)+(2bh(x)-1-1)
28、+1= 2bh(x)-1 即第点得证。证明bh(rootT)h/2， h为红黑树的树高红点的孩子必为黑/红黑树的性质4红点的层数h/2因此 = bh(rootT)h/2证明最后结论红黑树有n个内点由 = n2bh(rootT)-12h/2-1 = h2log(n+1) 4. 左旋算法(略)步骤解释：需要变动的是3根粗链 临界情形yrightx /记录指向y节点的指针rightxlefty, pleftyx /连到x右 =nilTpypx, px的左或右指针指向y /y连到px Px=nilT, 即x为根Leftyx, pxy /x连到y左注：-要注意先后顺序；-每条边的修改涉及双向；-要考虑临
29、界情形(特殊情形)；LeftRotate(T, x) /假定rightx nilTy rightx; /step rightx lefty; plefty x; /step py p x; /step if px=nilT then /x是根rootT y; /修改树指针else if x=leftpx then leftpx y; else rightpx y;lefty x; px y;/step T(n)=O(1)5. 插入算法的时间、至多使用2次旋转step 1 ：将z节点按BST树规则插入红黑树中，z是叶子节点；step 2 ：将z涂红；step 3 ：调整使其满足红黑树的性质； R
30、BInsert(T, z) y nilT; /y用于记录：当前扫描节点的双亲节点x rootT; /从根开始扫描while x nilT do /查找插入位置 y x; if keyzkeyx then /z插入x的左边x leftx;Else x rightx; /z插入x的右边pz y; /y是z的双亲if y= nilT then /z插入空树rootT z; /z是根elseif keyzkeyy then lefty z; /z是y的左子插入elserighty z; /z是y的右子插入leftz rightz nilT;colorzred;RBInsertFixup(T, z);时
31、间：T(n)=O(logn)调整算法的时间：O(logn);整个插入算法的时间：O(logn);调整算法中至多使用2个旋转lRBInsertFixup(T, z) while ( colorpz=red ) do /若z为根，则pz=nilT，其颜色为黑，不进入此循环 /若pz为黑，无需调整，不进入此循环if pz=leftppz then /case 1,2,3 y rightppz; /y是z的叔叔if colory=red then /case 1 colory=black; colorpz=black; colorppz=red; zppz;else /case 2 or case 3
32、 y为黑else /case 2 or case 3 y为黑 if z=rightpz then /case 2 z pz; /上溯至双亲leftRotate(T, z); /以下为case 3 colorpz=black; colorppz=red;RightRotate(T ppz); RightRotate(T, ppz); /pz为黑，退出循环 /case 1s endif /case 2 or 3 s else /case 4,5,6s 与上面对称 /end whilecolorroott black;6. 删除算法的时间、至多使用3次旋转RBDelete(T, z) if (lef
33、tz=nilT) or (rightz=nilT) then /case 1,2y z; /后面进行物理删除yelse /z的两子树均非空，case 3 y TreeSuccessor(z); /y是z的中序后继/此时，y统一地是x的双亲节点且是要删除节点 的双亲节点且是要删除节点/ x是待连接到py的节点，以下要确定xif lefty nilT then /本if语句综合了case1,2,3的xx lefty;Elsex righty; /以下处理：用x取代y与y的双亲连接px py;if py=nilT then /y是根rootT x; /根指针指向xelse /y非根if y=left
34、py then /y是双亲的左子leftpy x;elserightpy x;if yz then /case 3y的内容copy到z;if colory=black thenRBDeleteFixup(T, x); /调整算法return y; /实际是删除y节点调整算法：RBDeleteFixup(T, x)讨论x：或是y的唯一孩子；或是哨兵nilT 可以想象将y的黑色涂到x上，于是-若x为红，只要将其涂黑，调整即可终止；-若x为黑，将y的黑色涂上之后，x是一个双黑节点，违反性质1。处理步骤如下：step 1：若x是根，直接移去多余一层黑色(树黑高减1)，终止；step 2：若x原为红，将
35、y的黑色涂到x上，终止；step 3 ：若x非根节点，且为黑色，则x为双黑。通过变色、旋转使多余黑色向上传播，直到某个红色节点或传到根；RB-DELETE-FIXUP(T,x) /调整算法的时间：O(logn)ehile x != T.root and x.color = BLACKif x = x.p.leftw = x.p.rightif w.color = REDw.color=BLACKx.p.color=REDLEFT-ROTATE(T,x,p)w=x.p.rightif w.left.color = BLACK and w.right.color = BLACKw.color=RE
36、Dx = x.pelse if w.right.color = BLACKw.left.color = BLACKw.color = REDRIGHT-ROTATE(T,w)w = x.p.rightw.color = x.p.colorx.p.color = BLACKw.right.color = BLACKLEFT-ROTATE(T,x,p)x=T.rootelse(same as then clause with “right” and “left”exchanged)x.color = BlACK10 数据结构的扩张(ch14)1.动态顺序统计：扩展红黑树，支持选择问题(给定Rank
37、求相应的元素)，Rank问题(求元素x在集合中的Rank)(1)节点结构的扩展；OS树的定义：S(OrderStatistic)树是 棵红黑树在每个 OS(Order-Statistic)树是一棵红黑树在每个节点上扩充一个域sizex而得到的，它是以x为根的子树中内部节点的总数(包括x) 即子树大 根的子树中内部节点的总数(包括x)，即子树大小。节点结构：key/size(2)选择问题的算法；选择问题定义：在以x为根的子树中，查找第i个最小元素算法：OSSelect(x, i) (1): r sizeleftx+1;(2): 若i=r 则返回x (2): 若i=r，则返回x；若ir，则递归地在x的左子树中继续找第i个元素；若ir，则递归地在x的右子树中继续找第i-r个元素；时间：O(logn)(3)Rank问题的算法；求秩问题定义：OS树中，给定元素x求其rank算法：step 1: 在以x为根的子树中，x的秩：r sizeleftx+1； r sizeleftx+1；st
