习题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次； 若子节点有子节点2i, 则最多可交换2次； 若…..有子节点i×2, 则最多可交换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
k2
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
kk+1
复杂度:T(n)=T(?n/2?)+ T(?n/2?)≈2T(n/2) (设2≤n<2)
=…=2T(n/2) =2T(1) = n
k
k
k