摊还分析之聚合分析

[zhuanyongxigua]

先看聚合分析时摊还代价的定义：一个 n 个操作的序列最坏情况下花费的总时间为 T(n)，在最坏情况下，每个操作的平均代价，或摊还代价为 T(n)/n。

显而易见，聚合分析有两个关键点，一个是“n 个操作”，另一个是总时间“T(n)”。只要分析出了这两个量，就能轻易得到摊还代价。

但现实往往没有那么简单。

“n 个操作”是什么取决于你要分析的操作。比如变长数组的 PUSH，“n 个操作”显然就是 "n 个 PUSH 操作"，它不是“从首次 PUSH 到第一次扩容为止（即便结果与正确的分析一致）”，因为你需要分析的是 PUSH 操作的复杂复，这里面会出现多个普通的 PUSH，也可能会出现多个会触发扩容的 PUSH；如果分析一个每次代价不同的算法，那“n 个操作”就是把这个算法执行 n 次；

“T(n)”取决于你对你要分析的数据结构与算法的理解，这里一般没有固定的思路，不同的数据结构与算法，不同的问题，你可能需要不同的方法来分析，隐含的条件能找到的越多，得到的 T(n) 也就越准确。（很多情况下，分析 T(n) 的关键在于在 n 个操作中，代价较大的操作会出现的次数）

来看两个具体的例子：

变长数组的 PUSH 和 POP 操作的复杂度分析

初始条件为空数组，分配常数空间，它的扩容和缩容的策略是：当数组满时，扩容为原来的 2 倍；当数组的元素个数小于数组长度的 1/4 时，缩容为原来的 1/2。

先看 PUSH 操作：

"n 个操作"就是 n 个 PUSH 操作。

对于“T(n)”，我们先来分析在 n 个 PUSH 操作中会出现多少次扩容。最终数组中一定是有 n 个元素，所以它最近一次扩容只能发生在 n/2 和 n 之间。上一次的上一次发生在 n/4 和 n/2 之间。以此类推，最远的一次扩容发生在 1 和 2 之间。可见，发生了多少次扩容取决于有多少个这样的区间，具体的区间为一个节点为 n/2, n/4, n/8, ..., 1。他们的代价是：n/2，n/4，n/8，...，1，这是一个等比数列，求和公式为 $S = a \frac{1 - r^n}{1 - r}$，代入得 $S = \frac{n}{2} \cdot \frac{1 - \frac{1}{2}^{\log_2 n}}{1 - \frac{1}{2}}$，结果为 n - 1。其余常规 PUSH 的代价的和可以认为是 n，所以 T(n) = 2n - 1， 摊还代价为 (2n - 1)/n，为 O(1)。

再看 POP 操作：

"n 个操作"就是 n 个 POP 操作。

对于“T(n)”，在 n 个 POP 操作中，由于是在不足 25% 的时候缩小到 1/2，与 PUSH 操作类似，也是一个等比数列，对于会触发缩容的 POP 操作，初始值为 n/4，公比为 1/2，数量为 $\log_2 n$，带入求和公式，最后结果与 PUSH 操作相同，摊还代价也为 O(1)。

一个二进制计数器加减法的分析

这里举《算法导论》中的例子，一个二进制计数器，n 个包含 INCREMENT 和 DECREMENT 操作的运行时间。注意这里说的是运行时间（其实就是 17.1-2 的题解），不是复杂度，书中分析复杂度是只分析 INCREMENT 的摊还代价。

此二进制计数器的的位宽是 k，每一位储存在一个数组 A 中，最低位保存在 A[0]，最高位在 A[k-1] 中，当溢出时，计数器将归零，类似的，为 0 时再减 1，会得到一个全 1 的结果（即模 $2^k$ 的计数器）。

加减法的代码如下：

function INCREMENT(A) {
  let i = 0
  while (i < A.length && A[i] === 1) {
    A[i] = 0
    i++
  }
  if (i < A.length) {
    A[i] = 1
  }
}

function DECREMENT(A) {
  let i = 0
  while (i < A.length && A[i] === 0) {
    i++
  }
  if (i < A.length) {
    A[i] = 0
    // 注意细节的话还要考虑越界问题，这里忽略
    A[i - 1] = 1
  }
}

分析思路同上，先搞清楚“n 个操作”和 T(n)。这里 n 个操作是已知条件，是一组包含 INCREMENT 和 DECREMENT 的操作序列，具体里面有多少个 INCREMENT 和 DECREMENT 操作，我们不知道，但是我们可以通过分析来得到 T(n)。

我们一般只会关心最坏情况。在这种情况下，最坏情况会发生在初始值全为 1，然后第一个操作为 INCREMENT，下一个操作为 DECREMENT，以此类推，交替进行。或者初始值为 0，先操作 DECREMENT，下一个是 INCREMENT，以此类推。在这两种情况下，每一个操作的代价都是 k，一共有 n 个操作，所以 T(n) = nk。