算法导论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, … 的操作交替执行，那么每一次操作都会使得全部比特翻转，此时总运行时间恰好为$\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)$。