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

13.10 设计一个回溯算法来生成数字1,2,…,n的所有排列。

输入：数字1,2,…,n

输出：数字1,2,…,n的所有排列c[1,…,n]向量 1. for k ←1 to n 2. c[k] ←0 3. end for 5. k ←1 6.while k≥1

7. while c[k]≤n-1 8. c[k] ←c[k]+1

9. if c为合法的then output c (and goto 12) 10. else if c为部分解 then k ←k+1 11. end while 12. c[k] ←0 13. k ←k-1 14. 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←0

2. while(low ?high) and (j=0)

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

5. else if x

时间复杂度分析

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

(n)?1n?nC?1?C(k?1)?C(n?k)?k?1?1?1nn??C(k?1)?C(n?k)?k?1?1?1?n-1n-1n??C(j)??j?1?C(j)??j?1?2n-1

?1?n?C(j)j?1nC(n) = n + 2{C(1)+C(2)+…+C(n-2) +C(n-1)} (n-1)C(n-1)= n-1 + 2{C(1)+C(2)+…+C(n-2)} (2)-(1) ? nC(n) - (n-1)C(n) = 1 + 2C(n-1) ?

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

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

C(n)?1n?n?1nC(n?1)?1n?n?1?1n??n-1+nn-1C(n-2)????1n?n?1n?1n(n?1)?n?1C(n?2)?1n?n?1n(n?1)?n?1?n?1?1?n-2+n-1n-2C(n-3)????1n?n?1n(n?1)?n?1(n?1)(n?2)?n?1n?2C(n?3)?...(*)

(*)