算法分析习题ppt课件.ppt

《算法分析习题ppt课件.ppt》由会员分享，可在线阅读，更多相关《算法分析习题ppt课件.ppt（42页珍藏版）》请在三一办公上搜索。

1、算法分析习题课,1,计算机算法分析习题课,第四章：2 、3、 5、6、10 第五章：2、3 、8 、 9 、11 、 12,算法分析习题课,2,4-2,算法分析习题课,3,4-2,当g(n)=O(1)和f(n)=O(n)时不妨设g(n)=a，f(n)=bn，则：T(n)=2T(n/2)+bn =4T(n/4)+2bn = = 2kT(n/2k)+kbn=an+bnlog2n=O(nlog2n),算法分析习题课,4,4-2,当g(n)=O(1)和f(n)=O(1)时，不妨设g(n)=c，f(n)=d，则：T(n)=2T(n/2)+d = 4T(n/4)+2d =2kT(n/2k)+kd = =c

2、n+d log2n =O(n),算法分析习题课,5,4-3,根据2.2节开始所给出的二分检索策略，写一个二分检索的递归过程。,算法分析习题课,6,Procedure BINSRCH(A, low, high, x, j)integer midif lowhigh then mid (low+high)/2 case : x=A(mid): jmid;return : xA(mid): BINSRCH(A, mid+1, high, x, j) : xA(mid): BINSRCH(A, low, mid-1, x, j) endcaseelse j0;endifend BINSRCH,算法分析

3、习题课,7,4-5,作一个“三分”检索算法，它首先检查n/3处的元素是否等于某个x的值，然后检查2n/3处的元素。这样，或者找到x，或者把集合缩小到原来的1/3。分析算法在各种情况下的计算复杂度。,算法分析习题课,8,Procedure ThriSearch(A, n, x, j)integer low, high, p1, p2low1; highnwhile lowhigh dop1(high+2low)/3p2(2high+low)/3case :x=A(p1): jp1;return :x=A(p2): jp2;return :xA(p2): lowp2+1 :else: lowp1+

4、1; highp2-1 endcaserepeatj0end ThriSearch,算法分析习题课,9,时间复杂度,成功:O(1),O(log3(n),O(log3(n)最好，平均，最坏失败:O(log3(n),O(log3(n),O(log3(n)最好，平均，最坏,算法分析习题课,10,4-6,对于含有n个内部结点的二元树，证明E=I+2n其中，E，I分别为外部和内部路径长度。证明：数学归纳法当n=1时，易知E=2，I=0，所以E=I+2n成立；假设nk(k0)时，E=I+2n成立；,算法分析习题课,11,则当n=k+1时，不妨认定某个内结点x，而且它为叶结点（一定存在这样的x，且设该结点的

5、层数为h），将结点x及其左右子结点（外结点）从原树中摘除（x替换为外结点）。,新树内部结点为k个,满足：Ek=Ik+2k (1)原树的内、外部路径长度：Ek+1= Ek-h+2(h+1) (2)Ik+1=Ik+h (3)综合(1)(2)(3)式：Ek+1= Ik+2k+h+2 = Ik+1- h+2k+h+2= Ik+1+2(k+1)故命题成立。,算法分析习题课,12,4-10,过程MERGESORT的最坏情况时间是O(nlogn)，它的最好情况时间是什么？能说归并分类的时间是(nlogn)吗？,算法分析习题课,13,基于分治策略的算法-归并分类,Procedure MERGESORT(low

6、,high) if lowhigh then mid(low+high)/2 call MERGESORT(low,mid) call MERGESORT(mid+1,high) call MERGE(low,mid,high) endifEnd MERGESORT,算法分析习题课,14,最好情况：对有序文件进行排序分析递归的次数不会发生变化-log(n)次归并中比较的次数会发生变化（两个长n/2序列归并）最坏情况两个序列交错大小需要比较n-1次最好情况一个序列完全大于/小于另一个序列比较n/2次差异都是线性的，不改变复杂性的阶最好情况时间是O(nlogn) ，平均复杂度O(nlogn)。,算

7、法分析习题课,15,第五章：2、3 、8 、 9 、11 、 12,算法分析习题课,16,5-2,求以下情况背包问题的最优解，n=7，m=15，(p1 , p7)=(10,5,15,7,6,18,3)和(w1,w7) = (2,3,5,7,1,4,1)。按照pi/wi的非增序可得(p5/w5,p1/w1,p6/w6, p3/w3,p7/w7,p2/w2,p4/w4)=(6,5,9/2,3,3,5/3,1)所以最优解为:(1,2/3,1,0,1,1,1) 且FO(I)= 166/3,算法分析习题课,17,5-2,将以上数据情况的背包问题记为I。设FG(I)是物品按pi的非增次序输入时由GREED

8、Y-KNAPSACK所生成的解，FO(I)是一个最优解。问FO(I)/ FG(I)是多少?按照Pi的非增次序输入时，得(p6,p3,p1,p4,p5,p2, p7)=(18,15,10,7,6,5,3)，对应的(w6,w3,w1,w4,w5, w2,w7)=(4,5,2,7,1,3,1). 则FG(I)的解为(1,0,1,4/7,0,1,0),FG(I)=47 所以FO(I)/FG(I)= 166/141.,算法分析习题课,18,5-2,当物品按wi的非降次序输入时，重复的讨论。按照wi的非增次序输入时，得到(w5,w7,w1, w2,w6,w3,w4)=(1,1,2,3,4,5,7)，相应的

9、(p5,p7,p1, p2,p6,p3,p4)=(6,3,10,5,18,15,7) 则FW(I)的解为(1,1,4/5,0,1,1,1), FW(I)= 54 所以FO(I)/ FW(I)=83/81.,算法分析习题课,19,5-3,(0/1背包问题)如果将3.3节讨论的背包问题改成 这种背包问题称为0/1背包问题。它要求物品或者整件装入背包或者整件不装入。求解此问题的一种贪心策略是：按pi/wi的非增次序考虑这些物品，只要正被考虑的物品能装的进就将其装入背包。证明这种策略不一定能得到最优解。,算法分析习题课,20,5-3,证明：当按照pi/wi的非增次序考虑物品存放背包时，如果所装入的物品

10、恰能装满背包时，显然为最优解，否则未必是最优解.可举例如下：设n=3,M=6, (p1,p2,p3)=(3,4,8),(w1,w2,w3)=(1,2,5) 按照pi/wi 的非增序得到 (p1/w1,p2/w2,p3/w3)=(3,2,1.6)，则其解为(1,1,0)，而事实上最优解是(1,0,1) 。问题得证。,算法分析习题课,21,5-8, 当n=7,(p1,p7)=(3,5,20,18,1,6,30) 和(d1,d7)= (1,3,4,3,2,1,2) 时，算法3.5所生成的解是什么？解：pi的非增序列(p7, p3, p4, p6, p2, p1, p5) =(30,20,18,6,5

11、,3,1)，对应的期限为(2,4,3,1,3,1,2)，按照算法3.5生成的解为：J(1)=7(2), J(1)=7(2), J(2)=3(4)；J(1)=7(2), J(2)=4(3),J(3)=3(4)；J(1)=6(1), J(2)=7(2),J(3)=4(3),J(4)=3(4)；,算法分析习题课,22,5-8, 证明即使作业有不同的处理时间定理3.5亦真。这里，假定作业i的效益pi0，要用的处理时间ti0，限期diti. 定理3.5:设J是k个作业的集合, =i1i2ik是J中作业的一种排序,它使得di1di2dik .J是一个可行解,当且仅当J中的作业可以按照的次序又不违反任何一个

12、期限的情况来处理.,算法分析习题课,23,5-8,证明：显然对于ti0（diti），如果J中的作业可以按照的次序而又不违反任何一个期限来处理，即对次序中的任一个作业k，应满足dk ，则J就是一个可行解。 下面证明如果J是可行解， =i1i2ik使得J中的作业可以按照di1di2dik 排列而又不违反任何一个期限。,算法分析习题课,24,5-8,J是可行解，则必存在=r1r2rk，使得对任意ri，都有 di ，设是按照di1di2dik排列的作业序列i1i2ik.假设，那么令a是使raia的最小下标，设rb=ia，显然ba，在中将ra与rb交换，因为drbdra，显然ra和rb可以按期完成.还要

13、证明ra和rb之间的作业也能按期完成。因为drbdra，且对二者之间的所有作业rt，都有drbdrt，又由于是可行解，所以 显然 ，作业ra和rb交换后，所有作业均不违反期限值。连续使用这种方法，就可转换成且不违反任何一个期限，定理得证。,算法分析习题课,25,5-9, 对于3.4节的作业排序问题证明：当且仅当子集合J中的作业可以按下述规则处理时它表示一个可行解；如果J中的作业i还没分配处理时间，则将它分配在时间片a-1，a处理，其中a是使得1rdi的最大整数r，且时间片a-1，a是空的。,算法分析习题课,26,5-9,易证如果J中的作业能按上述规则处理，显然J是可行解；如果J是可行解，根据定

14、理3.5可知，J中的作业根据时间期限的非降次序排列，得到i1i2ik in ，并且按照这个顺序，可以处理J中所有作业，而对这一序列中的任意作业ik，如果它的时间期限是dk，且时间片dk-1,dk是空的，则分配之；若时间片dk-1，dk非空，则向前找最大的非空r-1,r时间片，1rdk因为J是可行解，所以一定可以找到此时间片。故命题得证。,算法分析习题课,27,5-9, 仿照例3.5的格式，在习题8所提供的数据集上执行算法3.6。n=7, (p1,p7)=(3,5,20,18,1,6,30) , (d1,d7)= (1,3,4,3,2,1,2)(p7, p3, p4, p6, p2, p1, p

15、5)=(30,20,18,6,5,3,1)， 对应的期限为(2,4,3,1,3,1,2)b=min n,maxd(i) =min7,4 =4,28,空,7,7,3,(p7, p3, p4, p6, p2, p1, p5)=(30,20,18,6,5,3,1)，对应的期限为(2,4,3,1,3,1,2),29,(p7, p3, p4, p6, p2, p1, p5)=(30,20,18,6,5,3,1)，对应的期限为(2,4,3,1,3,1,2),7,3,4,7,3,4,6,算法分析习题课,30,5-11, 证明如果一棵树的所有内结点的度都为k，则外结点数n满足n mod (k-1)=1.证明：

16、 设某棵树内结点个数是i，外结点个数是n，边的条数是e，则有 e=i+n-1 ik=e ik=i+n-1 (k-1)i=n-1 n mod (k-1)=1,算法分析习题课,31,5-11, 证明对满足 n mod (k-1)=1的正整数n，存在一棵具有n个外结点的k元树T(在一棵k元树中，每个结点的度至多为k)。进而证明T中所有内结点的度为k.,算法分析习题课,32,5-11,利用数学归纳法(m表示外结点数目)。当m =k时，存在外结点数目为k的k元树T，并且T中内结点的度为k；,m=33mod(3-1)=1,算法分析习题课,33,假设当 m n，且满足m mod (k-1)=1时，存在一棵具

17、有m个外部结点的k元树T，且所有内部结点的度为k；我们将外部结点数为m的符合上述性质的树T中某个外部结点用内部结点a替代，且结点a生出k个外部结点.,算法分析习题课,34,易知新生成的树T中外部结点的数目为n= m-1+k=m+(k-1)，因为 m mod (k-1)=1，显然n为满足n mod (k-1)=1，且比m大的最小整数。树T每个内结点的度为k，所以n=m+(k-1)时，存在符合上述性质的树。故命题得证。,算法分析习题课,35,5-12, 证明如果n mod (k-1)=1，则在定理3.6后面所描述的贪心规则对于所有的(q1,q2,qn)生成一棵最优的k元归并树。(P84),算法分析

18、习题课,36,5-12,通过数学归纳法证明：对于n=k，返回一棵只有一个内部结点的树，这棵树显然是最优的。假定该算法对于(q1,q2,qm)，其中m=(k-1)s+1 (s0)，生成一棵最优树则只需证明对于(q1,q2,qn)，其中n=(k-1)(s+1) +1=m+k-1，也能生成最优树即可,算法分析习题课,37,不失一般性，假定q1q2qn，且q1,q2,qk是算法所找到的k棵树的WEIGHT信息段的值。于是q1,q2,qk可生成子树T.设T是一棵对于(q1,q2,qn)的最优k元归并树。设P是距离根最远的一个内部结点。如果P的k个儿子不是q1,q2,qk，则可以用q1,q2,qk和P现在

19、的儿子进行交换，这样不增加T的带权外部路径长度。因此,T也是一棵最优归并树中的子树。,算法分析习题课,38,在T中如果用其权为q1+q2+qk的一个外部结点来代换T，则所生成的树T是关于(T,qk+1,qn)的一棵最优归并树。由归纳假设，在使用其权为q1+q2+qk的那个外部结点代换了T以后，过程TREE求的是关于(T,qk+1,qn)的最优归并树。因此TREE生成一棵关于(q1,q2,qn)的最优归并树。,算法分析习题课,39,P97-12, (q1,q2,q11)=(3,7,8,9,15,16,18,20,23,25,28)时，画出使用这一规则所得到的最优3元归并树。,40,（q1,q2,q11）=（3,7,8,9,15,16,18,20,23,25,28）,41,（q1,q2,q11）=（3,7,8,9,15,16,18,20,23,25,28）,42,7,8,3,23,25,28,9,15,16,18,20,18,40,56,76,172,（q1,q2,q11）=（3,7,8,9,15,16,18,20,23,25,28）,