算法导论第十七章习题解答

""" 1) let fai'(Di) = fai(Di)-fai(D0) Ci' = ci + fai'(Di) - fai'(Di-1) = ci + fai(Di)-fai(D0) - (fai(Di-1)-fai(D0)) = ci + fai(Di) - fai(Di-1) = Ci 得证 """ """ 2) fai(Di) = 2*i - 2^(1+floor(lgi)) 当i 不为 2的指数倍时： ci' = ci + fai(Di) - fai(Di-1) = 1 + 2*i - 2^(1+floor(lgi)) - 2*(i-1) + 2^(1+floor(lgi-1)) = 1 + 2*i - 2*(i-1) = 3 当 i为 2的指数倍时 i = 2^j： ci' = ci + fai(Di) - fai(Di-1) = i + 2*i - 2^(1+floor(lgi)) - 2*(i-1) + 2^(1+floor(lgi-1)) = i + 2*i - 2*(i-1) + 2^(1+j) - 2^(1+j-1) = i + 2 - i = 2 """ """ 3) """ """ 4) ci' = ci + fai(Di) - fai(Di-1) => ci = ci' + fai(Di-1) - fai(Di) sum(ci) = sum(ci') + D0 - Dn <= 2n + s0 - sn """ """ 5) 由式 17.4 和其后的结论有 sum(ci) = 2n - bn + b0 omega(b) = n => b = O(n) sum(ci) = O(n) """ """ 6) 参看10.1_6的代码实现 let fai(Di) = ni 表示队列中的元素 ENQUEUE 包含两个入栈动作和一个出栈 ci' = ci + fai(Di) - fai(Di-1) = 3+1 = 4 DEQUEUE 就是一个出栈操作 ci' = ci + fai(Di) - fai(Di-1) = 1-1 = 0 故摊还代价为O(1) """ """ 7) 插入元素花费为3，1用于插入本身，1用于线性查找，1保留 则保留在数组中元素的保持有信用2 执行删除时，找到中位数并删除大半，将保留的1叠加到剩余的元素上，则保留的信用为2 """