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

习题4.13

A1 A2 A3 A4 A5 A6 A7 A8 A9 10 11 12 13 14 15 16 17 18 19

(b)元素最大交换次数：A9~A5 各1次；A4~A3 各2次；A2最多3次；A1最多4次?最多共需16次元素交换

4.13另解：

考虑第i个节点，其子节点为2i，则最多可交换1次； 若子节点有子节点22i, 则最多可交换2次； 若…..有子节点i×2, 则最多可交换k次；

k

因此有

i×2 ≤ 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次

k

6.5 用分治法求数组A[1…n]元素和，算法的工作空间是多少？ 输入：数组A[1…n]

输出：数组的所有元素之和∑A[i] {i=1…n}

SUM(low, high)

1. if high = low then 2. return A[low] 3. else

4. mid←?(low+high)/2? 5. s1←SUM(low,mid) 6. s2←SUM(mid+1, high) 7. return s1+s2 8. end if

工作空间：mid~?(logn), s1&s2~?(1)（后序遍历树，不断释放空间，故为常数?(1)），总的工作空间为?(logn).

6.6 用分治法求元素x在数组A中出现的频次。 freq(A[low, high], x) 1. if high=low then 2. if A[low]=x then 3. return 1 4. else

5. return 0 6. end if 7. else

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

复杂度:T(n)=T(?n/2?)+ T(?n/2?)≈2T(n/2) (设2k≤n<2k+1)

=…=2kT(n/2k) =2kT(1) = n