算法分析习题

算法分析习题课1计算机算法分析—习题课第四章：2、3、5、6、10第五章：2、3、8、9、11、12算法分析习题课24-2在下列情况下求解2.1节的递归关系式T(n)=()2(/2)()gnnTnfn足够小否则当①g(n)=O(1)和f(n)=O(n)；②g(n)=O(1)和f(n)=O(1)。算法分析习题课34-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)算法分析习题课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)+kd=…=cn+dlog2n=O(n)算法分析习题课54-3根据2.2节开始所给出的二分检索策略，写一个二分检索的递归过程。算法分析习题课6ProcedureBINSRCH(A,low,high,x,j)integermidiflow≤highthenmid←(low+high)/2case:x=A(mid):j←mid;return:xA(mid):BINSRCH(A,mid+1,high,x,j):xA(mid):BINSRCH(A,low,mid-1,x,j)endcaseelsej←0;endifendBINSRCH算法分析习题课74-5作一个“三分”检索算法，它首先检查n/3处的元素是否等于某个x的值，然后检查2n/3处的元素。这样，或者找到x，或者把集合缩小到原来的1/3。分析算法在各种情况下的计算复杂度。算法分析习题课8ProcedureThriSearch(A,n,x,j)integerlow,high,p1,p2low←1;high←nwhilelow≤highdop1←(high+2low)/3p2←(2high+low)/3case:x=A(p1):j←p1;return:x=A(p2):j←p2;return:xA(p1):high←p1-1:xA(p2):low←p2+1:else:low←p1+1;high←p2-1endcaserepeatj←0endThriSearch算法分析习题课9时间复杂度成功:O(1),O(log3(n)),O(log3(n))最好，平均，最坏失败:O(log3(n)),O(log3(n)),O(log3(n))最好，平均，最坏算法分析习题课104-6对于含有n个内部结点的二元树，证明E=I+2n其中，E，I分别为外部和内部路径长度。证明：数学归纳法当n=1时，易知E=2，I=0，所以E=I+2n成立；假设n≤k(k0)时，E=I+2n成立；算法分析习题课11则当n=k+1时，不妨认定某个内结点x，而且它为叶结点（一定存在这样的x，且设该结点的层数为h），将结点x及其左右子结点（外结点）从原树中摘除（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)故命题成立。算法分析习题课124-10过程MERGESORT的最坏情况时间是O(nlogn)，它的最好情况时间是什么？能说归并分类的时间是Θ(nlogn)吗？算法分析习题课13基于分治策略的算法-归并分类ProcedureMERGESORT(low,high)iflowhighthenmid←(low+high)/2callMERGESORT(low,mid)callMERGESORT(mid+1,high)callMERGE(low,mid,high)endifEndMERGESORT算法分析习题课14最好情况：对有序文件进行排序分析递归的次数不会发生变化----log(n)次归并中比较的次数会发生变化（两个长n/2序列归并）最坏情况两个序列交错大小需要比较n-1次最好情况一个序列完全大于/小于另一个序列比较n/2次差异都是线性的，不改变复杂性的阶最好情况时间是O(nlogn)，平均复杂度O(nlogn)。算法分析习题课15第五章：2、3、8、9、11、12算法分析习题课165-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算法分析习题课175-2②将以上数据情况的背包问题记为I。设FG(I)是物品按pi的非增次序输入时由GREEDY-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.算法分析习题课185-2．③当物品按wi的非降次序输入时，重复②的讨论。按照wi的非增次序输入时，得到(w5,w7,w1,w2,w6,w3,w4)=(1,1,2,3,4,5,7)，相应的(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.算法分析习题课195-3(0/1背包问题)如果将3.3节讨论的背包问题改成这种背包问题称为0/1背包问题。它要求物品或者整件装入背包或者整件不装入。求解此问题的一种贪心策略是：按pi/wi的非增次序考虑这些物品，只要正被考虑的物品能装的进就将其装入背包。证明这种策略不一定能得到最优解。11iiiWMX01,P0,W0iiiniiinPXX目标函数：极大化约束条件：或算法分析习题课205-3证明：当按照pi/wi的非增次序考虑物品存放背包时，如果所装入的物品恰能装满背包时，显然为最优解，否则未必是最优解.可举例如下：设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)。问题得证。算法分析习题课215-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,3,1)，对应的期限为(2,4,3,1,3,1,2)，按照算法3.5生成的解为：1.J(1)=7(2),2.J(1)=7(2),J(2)=3(4)；3.J(1)=7(2),J(2)=4(3),J(3)=3(4)；4.J(1)=6(1),J(2)=7(2),J(3)=4(3),J(4)=3(4)；算法分析习题课225-8②证明即使作业有不同的处理时间定理3.5亦真。这里，假定作业i的效益pi0，要用的处理时间ti0，限期di≥ti.定理3.5:设J是k个作业的集合,=i1i2…ik是J中作业的一种排序,它使得di1≤di2≤…≤dik.J是一个可行解,当且仅当J中的作业可以按照的次序又不违反任何一个期限的情况来处理.算法分析习题课235-8证明：显然对于ti＞0（di≥ti），如果J中的作业可以按照的次序而又不违反任何一个期限来处理，即对次序中的任一个作业k，应满足dk≥，则J就是一个可行解。下面证明如果J是可行解，=i1i2…ik使得J中的作业可以按照di1≤di2≤…≤dik排列而又不违反任何一个期限。kjjt1算法分析习题课245-8J是可行解，则必存在’=r1r2…rk，使得对任意ri，都有di≥，设是按照di1≤di2≤…≤dik排列的作业序列i1i2…ik.假设’，那么令a是使raia的最小下标，设rb=ia，显然ba，在’中将ra与rb交换，因为drb≤dra，显然ra和rb可以按期完成.还要证明ra和rb之间的作业也能按期完成。因为drb≤dra，且对二者之间的所有作业rt，都有drb≤drt，又由于’是可行解，所以显然，作业ra和rb交换后，所有作业均不违反期限值。连续使用这种方法，’就可转换成且不违反任何一个期限，定理得证。1ijjt1btbirritdd1ttkrktd算法分析习题课255-9①对于3.4节的作业排序问题证明：当且仅当子集合J中的作业可以按下述规则处理时它表示一个可行解；如果J中的作业i还没分配处理时间，则将它分配在时间片[a-1，a]处理，其中a是使得1≤r≤di的最大整数r，且时间片[a-1，a]是空的。算法分析习题课265-9易证如果J中的作业能按上述规则处理，显然J是可行解；如果J是可行解，根据定理3.5可知，J中的作业根据时间期限的非降次序排列，得到i1i2…ik…in，并且按照这个顺序，可以处理J中所有作业，而对这一序列中的任意作业ik，如果它的时间期限是dk，且时间片[dk-1,dk]是空的，则分配之；若时间片[dk-1，dk]非空，则向前找最大的非空[r-1,r]时间片，1≤r≤dk因为J是可行解，所以一定可以找到此时间片。故命题得证。算法分析习题课275-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,p5)=(30,20,18,6,5,3,1)，对应的期限为(2,4,3,1,3,1,2)b=min{n,max{d(i)}}=min{7,4}=428F(0)F(1)F(2)F(3)F(4)01234-10-11-12-13-14F(0)F(1)F(2)F(3)F(4)01134-10-2112-13-14空{7}F(0)F(1)F(2)F(3)F(4)01133{7,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)01113{7,3,4}-10-41121334F(0)F(1)F(2)F(3)F(4)00113{7,3,4,6}10-51121334算法分析习题课305-11①证明如果一棵树的所有内结点的度都为k，则外结点数n满足nmod(k-1)=1.证明：设某棵树内结点个数是i，外结点个数是n，边的条数是e，则有e=i+n-1ik=eik=i+n-1(k-1)i=n-1nmod(k-1)=1算法分析习题课315-11②证明对满足nmod(k-1)=1的正整数n，存在一棵具有n个外结点的k元树T(在一棵k元树中，每个结点的度至多为k)。进而证明T中所有内结点的度为k.算法分析习题课325-11利用数学归纳法(m表示外结点数目)。当m=k时，存在外结点数目为k的k元树