算法导论16.2 Exercises 答案

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

16.2-1

执行PUSH操作时，需要花费\(1\)美元，此外还要额外预支\(1\)美元，这\(1\)美元是为后续的复制操作中充当信用。执行POP操作时，同样需要花费\(1\)美元，同样的，需要额外\(1\)美元为后面的复制操作充当信用。当真正执行复制操作时，PUSH和POP已经总共执行了\(k\)次元素，累积了\(k\)美元的预支，由于元素最多不超过\(k\)个，因此复制操作所需要的代价不超过\(k\)，所累积的信用足够支撑这次操作。因此，总共需要最多\(2n\)美元就能够完成这\(n\)次操作，因此每次操作的平均时间复杂度为\(O(1)\)。

16.2-2

令实际代价\(c_i\)为

\(c_i= \left \{\begin{aligned} &i & & \text{if}\quad \exists n\in \mathbb{N},i=2^n \\ &1 & & \text{otherwise} \end{aligned}\right.\)

这个时候的摊分策略是：每一次操作都需要支付\(3\)美元。也就是说，当\(i\)不是\(2\)的幂次的时候，还需要额外多支付\(2\)美元。

当\(i=1\)时，支付\(3\)美元足以支撑起这个操作，因为\(c_1=1\)；当\(i=2^n\)是一个\(2\)次幂时，我们证明\(2^{n-1}+1\sim 2^n\)中所有预支的代价总和可以支撑的起第\(i\)次实际操作的代价。\(2^{n-1}+1\sim 2^n-1\)这一部分都给\(i\)预支了\(2\)美元，总共预支了\((2\cdot 2^{n-1}-1)=2^n-2\)美元；再加上当前\(i=2^n\)所给的\(3\)美元，一共有\(2^n+1\)美元，这些支付的金额之和支撑得起第\(i\)次操作。因此，这种摊分方式是正确的，即\(\forall i\ge 1,\widehat{c_i}=3\)。

那么，实际代价之和满足\(\displaystyle{T(n)=\sum_{i=1}^n c_i\le \sum_{i=1}^n \widehat{c_i} = 3n}\)。平均每次操作的时间复杂度为\(\dfrac{T(n)}{n}=O(1)\)。

16.2-3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
INCREMENT(A, k)
  i = 0
  while i < k and A[i] == 1
    A[i] = 0
    i = i + 1
  if i < k
    A[i] = 1
    if i > A.p
      A.p = i
  else
    A.p = -1

// 假设数组A还有一个对象p，用于保存最高位的位置。
RESET(A)
  for i = 0 to A.p
    A[i] = 0
  A.p = -1

当执行INCREMENT时，只有循环结束时的一位才会发生从\(0\)变成\(1\)，这只会执行\(1\)次。这时将支付\(1\)美元。此外，也给这一位预支\(1\)美元，以保证此后这一位从\(1\)变成\(0\)；然后再多预支\(1\)美元，为将来执行RESET操作预支。此后执行INCREMENT时，某一位从\(1\)变成\(0\)不用支付任何开销。然后执行RESET时，之前预支过的每一位都将会设置成\(0\)。因此，所有操作的耗费总共不会超过\(3n\)美元，因此这\(n\)次操作的时间复杂度为\(O(n)\)。