算法导论16.1 Exercises 答案

发表于 更新于 分类于 阅读次数： 本文字数： 708 阅读时长 ≈ 1 分钟

16.1-1

相比于MULTIPOP操作，MULTIPUSH操作总是需要遍历完\(k\)个元素进行插入，它不能像MULTIPOP那样及时终止循环。总共插入的元素个数在\(n\)个操作以内可以达到\(\omega(n)\)的数量（如果\(k=\omega(n)\)），因此摊分下来的花费不能达到\(O(1)\)。

16.1-2

在最坏情况下，如果计数器的低\(k-1\)个比特全\(0\)，最高位比特为\(1\)，并且\(k\)个操作按照DECREMENT, INCREMENT, DECREMENT, ... 的操作交替执行，那么每一次操作都会使得全部比特翻转，此时总运行时间恰好为\(\Theta(nk)\)。

16.1-3

令\(T(n)\)表示这\(n\)次操作之和，那么分开考虑\(i\)是\(2\)的幂和\(i\)不是\(2\)的幂这两项，有

\(\begin{aligned} T(n)&=\sum_{i=0}^{\lfloor\lg n\rfloor} 2^i +\sum_{1\le i\le n,\nexists k\in \mathbb{Z} \text{ s.t. }2^k=1} 1\\ &=2^{\lfloor\lg n\rfloor+1} -1+\sum_{1\le i\le n,\nexists k\in \mathbb{Z} \text{ s.t. }2^k=1} 1\\ &\le 2^{\lg n+1}-1+\sum_{i=1}^n 1\\ &=2n-1+n\\ &\le 3n \end{aligned}\)

因此有\(T(n)=O(n)\)，平均每次操作的时间复杂度为\(\dfrac{T(n)}{n}=O(1)\)。