第十二讲 Amortized Analysis

均摊分析 Amortized Analysis

使用循环数组实现队列为什么不用链表实现？

  • 额外空间：每个节点都需要存储指针
  • 内存性能差：链表节点在内存中是分散的，这导致无效的缓存局部性。现代 CPU 在读取数据时会预取相邻内存，数组这种连续存储结构能极大地提高处理速度；而链表会导致频繁的“缓存未命中”。

当插入速度远快于删除速度时，数组会满，此时应当分配更大的数组。

  • 分配新空间：加倍数组长度。
  • 数据迁移：将原循环数组中的元素按顺序搬运到新数组的起始位置。
  • 代价：这次搬运操作需要 \(O(n)\) 的时间。

删除操作的时间复杂度为\(O(1)\)，插入操作的最差时间复杂度为\(O(n)\)。但是最差情况的出现频率较低。

均摊运行时间 (Amortized runtime)：对于一系列操作 \(o_1, o_2, \dots, o_n\)，其运行时间分别为 \(t_1, t_2, \dots, t_n\)，则单个操作的均摊运行时间为：\(\frac{1}{n} \sum_{i=1}^{n} t_i\)。

均摊分析的本质就是“取丰补歉”

  • 为什么不叫“平均运行时间” (Average runtime)？
    • 给定运行时间为 \(T(x)\) 的算法和输入分布 \(D\)。
    • 平均运行时间 = \(\mathbb{E}_{x \sim D}[T(x)]\)，这是针对输入分布进行的平均。
  • 为什么不叫“期望运行时间” (Expected runtime)？
    • 给定随机化算法，运行时间为 \(T(x, r)\)（\(r\) 为随机比特）。
    • 期望运行时间 = \(\mathbb{E}_{r}[T(x, r)]\)，这是针对算法内部随机性进行的期望。

均摊时间：不保证输入是随机的，算法也不是随机的。它是统计学意义上的“最坏情况序列”的总平均。无论用户输入什么样极端的数据，只要操作序列足够长，均摊成本就是确定的。

  • 如何形式化这种“罕见性”的直觉？
  • 下一次重新分配空间需要执行 \(\Omega(n)\) 次之后更多的插入操作。

聚合分析The aggregate method

案例一：动态数组扩容

将整个操作序列划分为多个区间，每个区间的终点是一次昂贵的“重新分配”。

  1. 假设上次扩容刚结束，数组大小为 \(2k\)，此时只有 \(k\) 个元素。
  2. 为触发下次扩容，必须再插入 \(j\) 个元素，直到填满空间。显然 \(j \ge k+1\)（即至少要走完剩余的一半空间）。
  3. 在这个区间内，总代价 = \(j\) 次普通插入（每次 \(O(1)\)）+ 1 次昂贵的扩容
  4. 总运行时间为 \(O(j + (k+j)) = O(j)\)。因为我们要平摊到 \(j\) 次插入操作上，所以均摊时间为 \(O(j) / j = O(1)\)。

**案例二：二进制计数器问题 **

一个布尔数组表示二进制数，初始全为 0，执行加 1 操作。代价为翻转的比特位数。虽然单次操作的最坏情况（如所有位都要进位，例如从 11...1 变成 100...0）是 \(O(\text{位数})\) 也就是 \(O(\log n)\)，但聚合分析告诉我们它其实是常数级的。考虑 \(n\) 次连续的加1操作：

第 \(i\) 位：每 \(2^i\) 次操作翻转一次。总次数 = \(n/2^i\)。 $\(T(n) = \sum_{i=0}^{\lfloor \log_2 n \rfloor} \frac{n}{2^i} = n \left( 1 + \frac{1}{2} + \frac{1}{4} + \dots \right) < 2n\)$ \(n\) 次操作的总代价小于 \(2n\)。因此，每次操作的均摊代价为 \(T(n)/n < 2\)

势能法（The potential method）

主要观察 ：代价高昂的操作是将许多 \(1\) 翻转为 \(0\)。每次操作仅将一个 \(0\) 翻转为 \(1\)。 为了以后能发生一次“昂贵”的操作（把一堆 \(1\) 变回 \(0\)），你必须先通过多次“廉价”的操作一个一个地把 \(0\) 变成 \(1\)。这些 \(1\) 就像是某种“燃料”或“能量”的积累。

  • 直觉：在一个代价高昂的操作之后，后续的操作在短期内不太可能再次变得高昂。

  • 方法：使用**势能函数 ** \(\Phi\) 来量化这种“可能性”。 对于一系列操作 \(o_1, o_2, \dots, o_n\)，其实际代价为 \(t_i\)。我们定义：

  • 势能函数 \(\Phi\)：必须满足 \(\Phi \ge 0\)（初始通常为 \(0\)）。

  • 均摊代价 (Amortized Cost / Charge) \(c_i\)： $\(c_i = t_i + (\Phi_{new} - \Phi_{old}) = t_i + \Delta\Phi\)$
    • 如果 \(\Delta\Phi > 0\)：实际操作很便宜，我们把多余的“精力”存入势能。
    • 如果 \(\Delta\Phi < 0\)：实际操作很贵，我们动用势能来顶替成本，使得 \(c_i\) 看起来依然很小。
    • \[\sum_{i=1}^n t_i = \sum_{i=1}^n (c_i - \Delta\Phi_i) = \left( \sum c_i \right) - (\Phi_{end} - \Phi_{init})$$ 由于 $\Phi_{end} \ge 0$，我们可以得出： $$\sum \text{实际代价} \le \sum \text{均摊代价} + \Phi_{init}\]

案例一：二进制计数器问题

定义势能函数 \(\Phi\)：设定 \(\Phi(A) = \text{计数器中 1 的个数}\)。显然 \(\Phi \ge 0\)。 假设初始状态有 \(k\) 个连续的 \(1\) 在末尾（例如 ...0111）。执行加 1 操作时：

  • 实际代价 \(t_i\)：这 \(k\) 个 \(1\) 变为了 \(0\)，且紧接着的一个 \(0\) 变为了 \(1\)。总翻转次数 \(t_i = k + 1\)。
  • 势能变化 \(\Delta\Phi\)：
    • 原来的 1 减少了 \(k\) 个。
    • 原来的 0 产生了一个新的 1。
    • 所以 \(\Delta\Phi = 1 - k\)。
  • 计算均摊代价 \(c_i\)： $\(c_i = t_i + \Delta\Phi = (k+1) + (1-k) = 2\)$ 使用势能法分析，每次操作的均摊代价恒等于 2。

案例二：循环队列插入元素的时间复杂度分析

当数组执行插入时，大部分情况是 \(O(1)\)，但偶尔会发生 \(O(n)\) 的扩容。我们需要设计一个势能函数 \(\Phi\)，使得： * 在普通插入时，\(\Phi\) 缓慢增加（存钱）。 * 在扩容发生时，\(\Phi\) 大幅减小（放钱），抵消掉搬运元素的 \(O(n)\) 成本。

关键：扩容显著降低了数组的“密度”。 * 数组快满时（\(n\) 接近 \(L\)），密度最高，势能应该达到峰值。 * 一旦扩容（\(L \to 2L\)），密度立即减半，势能也随之骤降。 * 这个“势能差”是用来支付搬运代价的。 * $\(\Phi = \frac{C \cdot n^2}{L}\)\(，其中：\)n$ = 当前元素数量。\(L\) = 当前数组总长度。\(C\) = 一个常数（用于对齐时间成本的量纲）。

删除操作实际代价 \(t_i = O(1)\)。势能变化 \(\Delta \Phi\)：\(n\) 变为 \(n-1\)，则 \(\Delta \Phi \approx \frac{C}{L}((n-1)^2 - n^2) \approx -\frac{2Cn}{L}\)。均摊代价：\(O(1) + (\text{负值}) = O(1)\)。

普通插入（不触发扩容）实际代价 \(t_i = O(1)\)。势能变化 \(\Delta \Phi\)：\(n\) 变为 \(n+1\)，则 \(\Delta \Phi \approx \frac{C}{L}((n+1)^2 - n^2) \approx \frac{2Cn}{L}\)。因为 \(n \le L\)（数组没满），所以 \(\frac{2Cn}{L} \le 2C\)，这也是一个常数。均摊代价：\(O(1) + O(1) = O(1)\)。

扩容操作 ：此时数组刚好填满，\(n = L\)。实际代价 \(t_i = O(n)\)（搬运 \(n\) 个元素）。势能变化 \(\Delta \Phi\)：\(n\) 不变，但 \(L\) 翻倍变为 \(2L\)。\(\Phi_{old} = \frac{Cn^2}{L}\)，\(\Phi_{new} = \frac{Cn^2}{2L}\)，$\(\Delta \Phi = \frac{Cn^2}{2L} - \frac{Cn^2}{L} = -\frac{Cn^2}{2L}\)$。

由于由于此时 \(n = L\)，代入得 \(\Delta \Phi = -\frac{Cn}{2}\)。

均摊代价：\(c_i = t_i + \Delta \Phi = O(n) - \frac{Cn}{2}\)。

只要我们选取的常数 \(C\) 足够大，这个值就会 \(\le 0\)。

分析动态数组扩容也可使用更简单的线性势能函数： $\(\Phi(n, L) = 2n - L\)$

  • 当 \(n = L/2\)（刚扩容完）时，\(\Phi = 0\)。
  • 当 \(n = L\)（准备扩容）时，\(\Phi = L\)。
  • 扩容到 \(2L\) 后，新势能 \(\Phi_{new} = 2n - 2L = 2L - 2L = 0\)。
  • \(\Delta \Phi = 0 - L = -L\)。这正好够支付搬运 \(L\) 个元素的 \(O(L)\) 代价。

使用二次项 \(\frac{n^2}{L}\) 是一种更广义的建模方式，它不仅能处理扩容，还能优雅地处理“缩容”（当元素太少时释放空间），保证了在各种动态调整下，均摊代价始终维持在 \(O(1)\)。

最终结论：无论数组如何伸缩，只要遵循“倍增”原则，序列操作的平均成本永远是常数。