算法分析习题

1、算法分析习题课1计算机算法分析计算机算法分析习题课习题课第四章：第四章：2 、3、 5、6、10 第五章：第五章：2、3 、8 、 9 、11 、 12算法分析习题课24-2算法分析习题课34-2 n当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) 算法分析习题课44-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)+

2、kd = =cn+d log2n =O(n)算法分析习题课54-3n根据根据2.2节开始所给出的二分检索策略，写一节开始所给出的二分检索策略，写一个二分检索的递归过程。个二分检索的递归过程。算法分析习题课6Procedure 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) endcas

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

4、+2low)/3 p2 (2high+low)/3 case :x=A(p1): jp1;return :x=A(p2): jp2;return :xA(p2): lowp2+1 :else: lowp1+1; highp2-1 endcaserepeatj0end ThriSearch算法分析习题课9时间复杂度时间复杂度n成功成功:qO(1),O(log3(n), O(log3(n)q最好，最好， 平均，平均，最坏最坏n失败失败:qO(log3(n),O(log3(n), O(log3(n)q最好，最好，平均，平均，最坏最坏算法分析习题课104-6对于含有对于含有n个内部结点的二元树，证明个

5、内部结点的二元树，证明E=I I+2n其中，其中，E，I I分别为外部和内部路径长度。分别为外部和内部路径长度。证明：数学归纳法证明：数学归纳法当当n=1时，易知时，易知E=2，I I=0，所以，所以E=I I+2n成立；成立；假设假设nk(k0)时，时，E=I I+2n成立；成立；算法分析习题课11 则当则当n=k+1时，不时，不妨认定某个内结点妨认定某个内结点x，而且它为叶结点而且它为叶结点（一定存在这样的（一定存在这样的x，且设该结点的层数且设该结点的层数为为h），将结点），将结点x及及其左右子结点（外其左右子结点（外结点）从原树中摘结点）从原树中摘除（除（x替换为外结替换为外结点）。点

6、）。X新树内部结点为新树内部结点为k个个,满足：满足：Ek=I Ik+2k (1)原树的内、外部路径长度：原树的内、外部路径长度：Ek+1= Ek-h+2(h+1) (2)I Ik+1=I Ik+h (3)综合综合(1)(2)(3)式：式：Ek+1= I Ik+2k+h+2 = I Ik+1- h+2k+h+2= I Ik+1+2(k+1)故命题成立。故命题成立。算法分析习题课124-10过程MERGESORT的最坏情况时间是O(nlogn)，它的最好情况时间是什么？能说归并分类的时间是(nlogn)吗？算法分析习题课13基于分治策略的算法基于分治策略的算法-归并分类归并分类nProcedur

7、e MERGESORT(low,high)Procedure MERGESORT(low,high) if lowhigh then if low0,W 0 iii niii nPXX 目标函数：极大化约束条件： 或算法分析习题课205-3n 证明：证明：q当按照当按照pi/wi的非增次序考虑物品存放背包时，的非增次序考虑物品存放背包时，如果所装入的物品恰能装满背包时，显然为最如果所装入的物品恰能装满背包时，显然为最优解，否则未必是最优解优解，否则未必是最优解.q可举例如下：可举例如下：设设n=3,M=6, (p1,p2,p3)=(3,4,8),(w1,w2,w3)=(1,2,5) 按照按照p

8、i/wi 的非增序得到的非增序得到 (p1/w1,p2/w2,p3/w3)=(3,2,1.6)，则则其解为其解为(1,1,0)，而事实上最优解是，而事实上最优解是(1,0,1) 。问题得证。问题得证。算法分析习题课215-8n 当当n=7,(p1,p7)=(3,5,20,18,1,6,30) 和和(d1,d7)= (1,3,4,3,2,1,2) 时，算法时，算法3.5所生成的解是什么？所生成的解是什么？n解：解：pi的非增序列的非增序列(p7, p3, p4, p6, p2, p1, p5) =(30,20,18,6,5,3,1)，对应的期限为，对应的期限为(2,4,3,1,3,1,2)，按照

9、算法按照算法3.5生成的解为：生成的解为：nJ(1)=7(2), n J(1)=7(2), J(2)=3(4)；nJ(1)=7(2), J(2)=4(3),J(3)=3(4)；1.J(1)=6(1), J(2)=7(2),J(3)=4(3),J(4)=3(4)；算法分析习题课225-8n 证明即使作业有不同的处理时间定理证明即使作业有不同的处理时间定理3.5亦亦真。这里，假定作业真。这里，假定作业i的效益的效益pi0，要用的处，要用的处理时间理时间ti0，限期，限期diti. n定理定理3.5:设设J是是k个作业的集合个作业的集合, =i1i2ik是是J中作业的一种排序中作业的一种排序,它使得

10、它使得di1di2dik .J是是一个可行解一个可行解,当且仅当当且仅当J中的作业可以按照中的作业可以按照 的的次序又不违反任何一个期限的情况来处理次序又不违反任何一个期限的情况来处理.算法分析习题课235-8n证明：显然对于证明：显然对于ti0（diti），如果），如果J中的作中的作业可以按照业可以按照 的次序而又不违反任何一个期限的次序而又不违反任何一个期限来处理，即对来处理，即对 次序中的任一个作业次序中的任一个作业k，应满，应满足足dk ，则，则J就是一个可行解。就是一个可行解。 下面证明如果下面证明如果J是可行解，是可行解， =i1i2ik使得使得J中中的作业可以按照的作业可以按照d

11、i1di2dik 排列而又不违排列而又不违反任何一个期限。反任何一个期限。kjjt1算法分析习题课245-8nJ J是可行解，则必存在是可行解，则必存在 =r=r1 1r r2 2rrk k，使得对任意，使得对任意r ri i，都有，都有 d di i ，设，设 是按照是按照d di1i1ddi2i2ddikik排列的作业序排列的作业序列列i i1 1i i2 2iik k. .假设假设 ，那么令，那么令a a是使是使r ra a i ia a的最小下标，的最小下标，设设r rb b=i=ia a，显然，显然baba，在，在 中将中将r ra a与与r rb b交换，因为交换，因为d drbr

12、bddrara，显然显然r ra a和和r rb b可以按期完成可以按期完成. .n还要证明还要证明r ra a和和r rb b之间的作业也能按期完成之间的作业也能按期完成。因为。因为d drbrbddrara，且对二者之间的所有作业且对二者之间的所有作业r rt t，都有，都有d drbrbddrtrt，又由于，又由于 是是可行解，所以可行解，所以 显然显然 ，作业，作业r ra a和和r rb b交换交换后，所有作业均不违反期限值。后，所有作业均不违反期限值。n连续使用这种方法，连续使用这种方法， 就可转换成就可转换成 且不违反任何一个期且不违反任何一个期限，定理得证。限，定理得证。1ij

13、jt1btbirritdd1ttkrktd算法分析习题课255-9n 对于对于3.4节的作业排序问题证明：当且仅当节的作业排序问题证明：当且仅当子集合子集合J中的作业可以按下述规则处理时它表中的作业可以按下述规则处理时它表示一个可行解；如果示一个可行解；如果J中的作业中的作业i还没分配处理还没分配处理时间，则将它分配在时间片时间，则将它分配在时间片a-1，a处理，其处理，其中中a是使得是使得1rdi的最大整数的最大整数r，且时间片，且时间片a-1，a是空的。是空的。算法分析习题课265-9n易证如果易证如果J中的作业能按上述规则处理，显然中的作业能按上述规则处理，显然J是可行是可行解；解；n如

14、果如果J是可行解，根据定理是可行解，根据定理3.5可知，可知，J中的作业根据中的作业根据时间期限的非降次序排列，得到时间期限的非降次序排列，得到i1i2ik in ，并且按，并且按照这个顺序，可以处理照这个顺序，可以处理J中所有作业，而对这一序列中所有作业，而对这一序列中的任意作业中的任意作业ik，如果它的时间期限是，如果它的时间期限是dk，且时间片，且时间片dk-1,dk是空的，则分配之；若时间片是空的，则分配之；若时间片dk-1，dk非非空，则向前找最大的非空空，则向前找最大的非空r-1,r时间片，时间片，1rdk因为因为J是可行解，所以一定可以找到此时间片。故命题得证。是可行解，所以一定

15、可以找到此时间片。故命题得证。 算法分析习题课275-9n 仿照例仿照例3.5的格式，在习题的格式，在习题8所提供的数据集上执所提供的数据集上执行算法行算法3.6。nn=7, (p1,p7)=(3,5,20,18,1,6,30) , (d1,d7)= (1,3,4,3,2,1,2)n(p7, p3, p4, p6, p2, p1, p5)=(30,20,18,6,5,3,1)， 对应的期限为对应的期限为(2,4,3,1,3,1,2)b=min n,maxd(i) =min7,4 =428F(0)F(1)F(2)F(3)F(4)01234-10-11-12-13-14F(0)F(1)F(2)F(

16、3)F(4)01134-10-2112-13-14空空7F(0)F(1)F(2)F(3)F(4)011337,3-10-2112-2334(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)F(0)F(1)F(2)F(3)F(4)011137,3,4-10-41121334F(0)F(1)F(2)F(3)F(4)001137,3,4,610-

17、51121334算法分析习题课305-11n 证明如果一棵树的所有内结点的度都为证明如果一棵树的所有内结点的度都为k，则外结点数则外结点数n满足满足n mod (k-1)=1.n证明：证明： 设某棵树内结点个数是设某棵树内结点个数是i，外结点个数，外结点个数是是n，边的条数是，边的条数是e，则有，则有 e=i+n-1 ik=e ik=i+n-1 (k-1)i=n-1 n mod (k-1)=1算法分析习题课315-11n 证明对满足证明对满足 n mod (k-1)=1的正整数的正整数n，存，存在一棵具有在一棵具有n个外结点的个外结点的k元树元树T(在一棵在一棵k元树元树中，每个结点的度至多为

18、中，每个结点的度至多为k)。进而证明。进而证明T中所中所有内结点的度为有内结点的度为k.算法分析习题课325-11n利用数学归纳法利用数学归纳法(m表示外结点数目表示外结点数目)。n当当m =k时，存在外结点数目为时，存在外结点数目为k的的k元树元树T，并，并且且T中内结点的度为中内结点的度为k；m=33mod(3-1)=1算法分析习题课33n假设当假设当 m n，且满足，且满足m mod (k-1)=1时，存时，存在一棵具有在一棵具有m个外部结点的个外部结点的k元树元树T，且所有内，且所有内部结点的度为部结点的度为k；n我们将外部结点数为我们将外部结点数为m的符合上述性质的树的符合上述性质的

19、树T中某个外部结点用内部结点中某个外部结点用内部结点 a替代，且结点替代，且结点a生出生出k个外部结点个外部结点.a算法分析习题课34n易知新生成的树易知新生成的树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)时，时，存在符合上述性质的树。故命题得证。存在符合上述性质的树。故命题得证。a算法分析习题课355-12n 证明如果证明如果n mod (k-1)=1，则在定理，

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