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

习题4.13

(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)1.if high = low then2.return A[low]3.else

4.mid←?(low+high)/2?5.s1←SUM(low,mid)6.s2←SUM(mid+1, high)

7.return s1+s28.end if

⼯作空间：mid~Θ(logn), s1&s2~Θ(1)（后序遍历树，不断释放空间，故为常数Θ(1)），总的⼯作空间为Θ(logn).6.6 ⽤分治法求元素x在数组A中出现的频次。freq(A[low, high], x)1.if high=low then2.if A[low]=x then3.return 14.else5.return 06.end if7.else

8.mid ←?(low+high)/2?9.f1 ←freq(A[low, mid])10.f2 ← freq(A[mid+1, high])11.return f1+f212.end if

复杂度:T(n)=T(?n/2?)+ T(?n/2?)≈2T(n/2) (设2k≤n<2k+1) =…=2k T(n/2k) =2k T(1) = n6.16修改后的MERGESORT算法最⼤⽐较次数(1)/2()2(/2)1n n if n m T nT n n if n m-≤=?+->

最⼩⽐较次数1()2(/2)/2n if n m C nC n n if n m-≤=?+>

令n/2k=m≥2，展开可知：T(n)= 2k T(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)=Θ(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) = 2k C(n/2k)+kn/2 = n/m×(m-1) + (n/2)log(n/m)= Θ(nlogn)6.35

split(A[low,...high])1. x←A[low] //备份为x2. while (low3. while (low0) --high;4. A[low] ←A[high]5. while (low6.A[high] ←A[low]7.}

8.A[low] ← x//这时, low=high7.3 动态规划法计算⼆项式系数kn

C ，并分析其时间复杂度。 1. for i←1 to n2. C[i,0] ← 1; C[i, i ] ←13. end for4. for i←2 to n

5. for j ←1 to i-1 / min(k, i-1) //例如计算C[6,2]6. C[i,j] ←C[i-1,j-1] + C[i-1,j]7. end8. end for

9. return C[n.k] 复杂度分析：212(1)(1)2nn

i j i i cn n c i c c i ====-=-===∑∑∑∑i-1n-121

Θ(n ) 或 212(1)n n

i j i c kc ck n =====-=∑∑∑k O(nk)

8.5硬币的⾯值为1, 2, 4, 8, ..., 2k, 要兑换的值n<2k+1，⽤贪⼼

算法解这个问题，要求算法复杂度为O(log n)

输⼊：k+1个不同硬币的⾯值，其中包括单位币（⾯值为1）输出：若要兑换的值n，给出各个⾯值硬币的数⽬num[0…k]1.将k+1个不同的⾯值按递增顺序排列，记为Value[0...k]2.num[0…k]←03.for j← k downto 04.num[j] ←?n/Value[j]?5.n←n - num[j]×Value[j]6.end for

7.return num[0…k]

8.16 修改Dijkstra算法，使它找出最短路径和它的长度。1. X={1}; Y←V-{1}; λ[1]←0; pre[1]←0;2. for y←2 to n

3. if y 相邻于1 then λ[y]←length[1,y]4. else λ[y]← ∞5. end if6. end for7. for j←1 to n-1

8. 令y∈Y, 使得λ[y]为最⼩的9. X←X∪{y}10. Y←Y - {y}11. for 每条边(y,w)

12. if w∈Y and λ[y]+length[y,w]< λ[w] then13. λ[w] ←λ[y]+length[y,w]14. pre[w] ← y14. end if15. end for16.end for输出最短路径

void PrintPath(int node) //输出格式为1→…→node{ if (node==1) print(“1”);else {

PrintPath( pre[node] ); //先递归再输出print(“→”, node);}}

着⾊向量c[1…n]是否是合法的。输⼊：图G=(V,E)，向量c[1…n]

输出：flag=true 若合法着⾊；否则flag=false2. for i←1 to n3. if c[i]≠0

4. for (i,j)∈E

5. if c[j]≠0 and c[j]=c[i]6. return false;7. end if8. end for9. end if10. end for11. return true

着⾊向量c[1…k]是否是部分的。输⼊：图G=(V,E)，向量c[1…k]

输出：true 若着⾊是部分的；否则输出false2. for i←1 to k3. if c[i]≠04. for (i,j)∈E

5. if j≤k and c[j]≠0 and c[j]=c[i]6. return false;7. end if8. end for9. end if10. end for11. return true

13.10 设计⼀个回溯算法来⽣成数字1,2,…,n的所有排列。输⼊：数字1,2,…,n输出：数字1,2,…,n的所有排列c[1,…,n]向量1. for k ←1 to n2. c[k] ←03. end for5. k ←16.while k≥17. while c[k]≤n-18. c[k] ←c[k]+1

9. if c为合法的then output c (and goto 12)10. else if c为部分解then k ←k+111. end while12. c[k] ←013. k ←k-114. end while

14.7 对⼆分查找算法进⾏随机化，即每次迭代时，随机选择剩下的位置代替搜索空间减半，假设在low与high之间每个位置被选中的概率都是相同的。⽐较这种随机化算法与⼆分查找的表现。输⼊：n个元素的升序数组A[1…n]和元素x输出：若x=A[j], 1≤j≤n, 则输出j, 否则输出0

1. low←1; high ←n; j←02.while(low ≤high) and (j=0)

3.mid ← ?( low+high)/2? / mid←random(low,high)4.if x=A[mid] then j ←mid5.else if x

6.else low ←mid+17.end while8.return j时间复杂度分析

将每次迭代时随机选择的位置记为k ，且在low 与high 之间每个位置被选中的概率都是1/n ，期望⽐较次数C(n)满⾜[][]11111

1()1(1)()11(1)()11()()21()nk n

k j j j C n C k C n k n C k C n k n C j C j n C j n ======+-+-=+-+-??=++ ?

=+∑∑∑∑∑n-1n-1n-1

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) ?11()(1)11111(2)(*)(1)1

111(1)11111(3)(*)(1)(1)(2)2...n C n C n n n

n n n n n C n n n n n n n n n n n n n n C n n n n n n n +=+-+??=+++=++---++??=++?--+++=+++-----=1n +C(n -2)n -1n -11n -1+C(n -3)n -2n -211()(2)111(2)1

11(2)121(2)11211121(1)(1)1(1)(2)(1)(2)

n C n C n n n n C n n n n C n n n n C n n n n n n n n n C n n n n n +=++--??+=++

-??-??+??=++-??-??+=+---+??=+?

--++++-=++------n +1n(n -1)n 1n(n -1)n(n -1)111n -1n -1n (*)1n -1+C(n -3)n -2n -2(3)21(3)1221(3)1231(3)22n n C n n n n C n n n n C n n n -??+=++-??--??+??=++-??--??+=+---n -12

+(n -1)(n -2)(n -1)(n -2)122+-n -2n -2n -1(*)11()(1)

21(2)1131(3)22...

11()2211//{()1}22n C n C n n n n C n n n n C n n n n n C n n C +=+-+=+---+=+---==-+=+-+=+==4n +1+C(n -4)n -3n -311n(可将C(n)=n 代⼊推导过程，以验证其正确性) 因此，随机化拟⼆分

查找的时间复杂度为O(n)，⼆分查找的时间复杂度为O(log n )。随机化⽅法的效率反⽽⽐⼆分查找低，其原因在于…

14.10 设L=x1,x2,…,x n是⼀个元素序列，其中元素x恰好出现k次（1≤k≤n），我们要找到⼀个j，使得x j=x。考虑重复执⾏下⾯的过程直到找到x 为⽌。⽣成⼀个1到n之间⾊随机数i，并检查是否x i=x。在平均情况下，这种⽅法和线性⽅法查找哪⼀种⽅法快？请说明。解：

(1) 随机查找的情况

不妨设第i1,i2,…,i k个元素等于x，记I={i1,i2,…,i k}, |I|=k, 则P{i∈I}=k/n，记p=k/n, q=1-p，则查找长度的数学期望E(ASL)=p×1+q×p×2+…+q i-1×p×i+…=1/p=n/k