算法导论 16.1 Exercises 答案

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, ... 的操作交替执行，那么每一次操作都会使得全部比特翻转，此时总运行时间恰好为 $\mathrm{\Theta }(nk)$。

16.1-3

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

$\begin{array}{rl}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{array}$

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