算法设计技巧与分析习题参考答案

习题4.13A1A1A2A3A6A7A4A5A8A910111213141516171819(b)元素最大交换次数：A9~A5各1次；A4~A3各2次；A2最多3次；A1最多4次Þ最多共需16次元素交换4.13另解：考虑第i个节点，其子节点为2i，则最多可交换1次；若子节点有子节点22i,则最多可交换2次；若…..有子节点i×2k,则最多可交换k次；因此有i×2k≤19求出满足上述不等式的最大的k值即可。i=1时,k=4;i=2时,k=3;i=3或4时,k=2;i=5~9时,k=1;因此最多交换4+3+2×2+1×5=16次

6.5用分治法求数组A[1…n]元素和，算法的工作空间是多少？输入：数组A[1…n]输出：数组的所有元素之和∑A[i]{i=1…n}SUM(low,high)ifhigh=lowthenreturnA[low]elsemid←ë(low+high)/2ûs1←SUM(low,mid)s2←SUM(mid+1,high)returns1+s2endif工作空间：mid~Q(logn),s1&s2~Q(1)（后序遍历树，不断释放空间，故为常数Q(1)），总的工作空间为Q(logn).6.6用分治法求元素x在数组A中出现的频次。freq(A[low,high],x)ifhigh=lowthenifA[low]=xthenreturn1elsereturn0endifelsemid←ë(low+high)/2ûf1←freq(A[low,mid])f2←freq(A[mid+1,high])returnf1+f2endif复杂度:T(n)=T(ën/2û)+T(én/2ù)≈2T(n/2)(设2k≤n<2k+1)=…=2kT(n/2k)=2kT(1)=n

6.16修改后的MERGESORT算法最大比较次数最小比较次数令n/2k=m≥2，展开可知：T(n)=2kT(n/2k)+kn-(2k-1)=n/m×m(m-1)/2+nlog(n/m)-n/m+1=n(m-1)/2+nlog(n/m)-n/m+1若T(n)=Q(nlogn),其中表达式有nm,nlogn,nlogm,n/m等.有n/m<nlogm<nm且须有nm=O(nlogn),i.e.,nm≤c·nlogn,则须有m≤c·logn.可令c=1,则m≤logn.另一方面，C(n)=2kC(n/2k)+kn/2=n/m×(m-1)+(n/2)log(n/m)=Q(nlogn)

6.35split(A[low,...high])1.x←A[low]//备份为x2.while(low<high){3.while(low<high&&A[high]>0)--high;4.A[low]←A[high]5.while(low<high&&A[low]≤0)++low;A[high]←A[low]}A[low]←x//这时,low=high

7.3动态规划法计算二项式系数，并分析其时间复杂度。1.fori←1ton2.C[i,0]←1;C[i,i]←13.endfor4.fori←2ton5.forj←1toi-1/min(k,i-1)//例如计算C[6,2]6.C[i,j]←C[i-1,j-1]+C[i-1,j]7.end8.endfor9.returnC[n.k]复杂度分析：或硬币的面值为1,2,4,8,...,2k,要兑换的值n<2k+1，用贪心算法解这个问题，要求算法复杂度为O(logn)输入：k+1个不同硬币的面值，其中包括单位币（面值为1）输出：若要兑换的值n，给出各个面值硬币的数目num[0…k]将k+1个不同的面值按递增顺序排列，记为Value[0...k]num[0…k]←0forj←kdownto0num[j]←n/Value[j]n←n-num[j]×Value[j]endforreturnnum[0…k]

8.16修改Dijkstra算法，使它找出最短路径和它的长度。1.X={1};Y←V-{1};λ[1]←0;pre[1]←0;2.fory←2ton3.ify相邻于1thenλ[y]←length[1,y]4.elseλ[y]←∞5.endif6.endfor7.forj←1ton-18.令y∈Y,使得λ[y]为最小的9.X←X∪{y}10.Y←Y-{y}11.for每条边(y,w)12.ifw∈Yandλ[y]+length[y,w]<λ[w]then13.λ[w]←λ[y]+length[y,w]14.pre[w]←y14.endif15.endfor16.endfor输出最短路径voidPrintPath(intnode)//输出格式为1→…→node{if(node==1)print(“1”else{PrintPath(pre[node]);//先递归再输出print(“→”,node);}}

13.2考虑3着色问题，给出一个算法判断一张图G=(V,E)的3着色向量c[1…n]是否是合法的。输入：图G=(V,E)，向量c[1…n]输出：flag=true若合法着色；否则flag=false2.fori←1ton3.ifc[i]≠04.for(i,j)∈E5.ifc[j]≠0andc[j]=c[i]6.returnfalse;7.endif8.endfor9.endif10.endfor11.returntrue

13.3考虑3着色问题，给出一个算法判断一张图G=(V,E)的3着色向量c[1…k]是否是部分的。输入：图G=(V,E)，向量c[1…k]输出：true若着色是部分的；否则输出false2.fori←1tok3.ifc[i]≠04.for(i,j)∈E5.ifj≤kandc[j]≠0andc[j]=c[i]6.returnfalse;7.endif8.endfor9.endif10.endfor11.returntrue

13.10设计一个回溯算法来生成数字1,2,…,n的所有排列。输入：数字1,2,…,n输出：数字1,2,…,n的所有排列c[1,…,n]向量1.fork←1ton2.c[k]←03.endfor5.k←16.whilek≥17.whilec[k]≤n-18.c[k]←c[k]+19.ifc为合法的thenoutputc(andgoto12)10.elseifc为部分解thenk←k+111.endwhile12.c[k]←013.k←k-114.endwhile14.7对二分查找算法进行随机化，即每次迭代时，随机选择剩下的位置代替搜索空间减半，假设在low与high之间每个位置被选中的概率都是相同的。比较这种随机化算法与二分查找的表现。输入：n个元素的升序数组A[1…n]和元素x输出：若x=A[j],1£j£n,则输出j,否则输出01.low←1;high←n;j←0while(low£high)and(j=0)mid←ë(low+high)/2û/mid←random(low,high)ifx=A[mid]thenj←midelseifx<A[mid]thenhigh←mid-1elselow←mid+1endwhilereturnj时间复杂度分析将每次迭代时随机选择的位置记为k，且在low与high之间每个位置被选中的概率都是1/n，期望比较次数C(n)满足nC(n)=n+2{C(1)+C(2)+…+C(n-2)+C(n-1)}(1)(n-1)C(n-1)=n-1+2{C(1)+C(2)+…+C(n-2)}(2)(2)-(1)nC(n)-(n-1)C(n)=1+2C(n-1)nC(n)=1+(n+1)C(n-1)

nC(n)=1+(n+1)C(n-1)

(可将C(n)=n代入推导过程，以验证其正确性)因此，随机化拟二分查找的时间复杂度为O(n)，二分查找的时间复杂度为O(logn)。随机化方法的效率反而比二分查找低，其原因在于…14.10设L=x1,x2,…,xn是一个元素序列，其中元素x恰好出现k次（1≤k≤n），我们要找到一个j，使得xj=x。考虑重复执行下面的过程直到找到x为止。生成一个1到n之间色随机数i，并检查是否xi=x。在平均情况下，这种方法和线性方法查找哪一种方法快？请说明。解：(1)随机查找的情况不妨设第i1,i2,…,ik个元素等于x，记I={i1,i2,…,ik},|I|=k,则P{i∈I}=k/n，记p=k/n,q=1-p，则查找长度的数学期望E(ASL)=p×1+q×p×2+…+qi-1×p×i+…=1/p=n/k(2)线性查找的情况其中，分母=n(n-1)(n-2)…(n-i+1)=n!/(n-i)!分子=(n-k)(n-k-1)…(n-k-i+2)×k×i=(n-k)!×k×i/(n-k-i+1)!则通项可写为于是，可以证明上式的成立。事实上，上式等价于即要证明成立。思路：右边变换→左边形式，另一方面，(*)其中将以上各式(除了*式)相加，即可得到即有成立。总结：随机查找，线性查找，因为，故线性查找更快。

14.16修改14.7节的随机抽样算法，使得它不再需要布尔数组S[1…n]，假设n比m大得多，比如n>m2.解：算法设计如下:1.k←12.whilek≤m3.r←random(1,n)4.i←k-15.whilei≥1andr≠A[i]6.i←i-17.endwhile8.ifi=09.A[k]←r10.k←k+111.endif12.endwhile复杂度分析如下:每次随机生成一个新元素r，要查找r是否已经出现在已经选定的数字中。设生成第i个有效随机数时，平均要产生E(Xi)次,则复杂度容易证明，且有因为m2<n,则，于是

14.16另解：算法设