在算法分析中，你是否遇到过这样的困境：某个数据结构的单次操作特别慢（比如动态表扩容、栈的批量弹出），但一系列操作的总时间却远低于最坏情况的累加？摊还分析（Amortized Analysis）正是为解决这类问题而生，而其中的势能法（Potential Method）凭借其直观的“能量”视角，成为最强大的分析工具之一。本文将通过栈、二进制计数器、动态表等经典案例，手把手教你如何定义势能函数、计算摊还代价，并掌握设计势能函数的一般原则。无论你是算法初学者还是有经验的开发者，都能从本文中学会用“势能”视角看穿操作序列的均摊代价。
为什么需要摊还分析？
以栈为例。假设栈支持 push、pop 和 multipop（批量弹出）三种操作。单次 multipop 的最坏代价是 $O(n)$（$n$ 为栈中元素个数），如果每次操作都是 multipop，总代价将达到 $O(n^2)$。然而，在真实的操作序列中，multipop 之前必然有足够多的 push 操作，因此总代价实际上是 $O(n)$。摊还分析要做的，就是证明这样一种上界：无论操作序列如何，总代价都不会超过某个与操作次数成正比的值。
摊还分析有三种等价方法：聚集法（Aggregate method）、记账法（Accounting method）和势能法（Potential method）。本文聚焦于势能法，因为它最适合处理复杂的数据结构。
势能法的核心思想
势能法的灵感来自物理学：你可以为数据结构定义一个“势能函数” $\Phi(S)$，它只依赖于当前状态 $S$。对于第 $i$ 次操作，其摊还代价 $\hat{c}_i$ 定义为：
$$ \hat{c}i = c_i + \Phi(S_i) - \Phi(S{i-1}) $$
其中 $c_i$ 是实际代价，$\Phi(S_i) - \Phi(S_{i-1})$ 是势能的变化量。
直观理解：如果一次操作消耗了大量资源（实际代价大），可以让它“消耗”一部分势能，从而降低摊还代价；反之，如果一次操作很快（实际代价小），它可以“积累”势能，为未来的高代价操作买单。这就是势能法的口诀：让消耗大的操作的势能大大的降。
只要初始势能 $\Phi(S_0) = 0$，且所有可达状态的势能都非负，那么总摊还代价就是总实际代价的一个上界。换言之，你只需证明每次操作的摊还代价为 $O(1)$，则总实际代价就是 $O(n)$。
势能法的一般步骤
- 选择势能函数：根据数据结构的状态，定义一个非负的势能函数 $\Phi$，且初始状态 $\Phi(S_0) = 0$。
- 验证非负性：确保在任何操作后 $\Phi(S) \ge 0$。
- 计算每种操作的摊还代价：对每种操作，计算实际代价 $c_i$ 和势能变化 $\Delta\Phi$，得出 $\hat{c}_i = c_i + \Delta\Phi$。
- 给出上界：如果每种操作的摊还代价都能被常数上界控制，则总实际代价不超过总摊还代价，从而得到均摊复杂度。
经典案例拆解
案例一：栈的 push/pop/multipop
- 势能函数：$\Phi(S) =$ 栈中元素个数。
- 初始状态：空栈，$\Phi = 0$。
- 操作分析：
- push(x)：实际代价 $1$，栈大小 $+1$，势能 $+1$ → 摊还代价 $= 1 + 1 = 2$。
- pop()：实际代价 $1$，栈大小 $-1$，势能 $-1$ → 摊还代价 $= 1 - 1 = 0$。
- multipop(k)：实际弹出 $t = \min(k, \text{size})$ 个元素，实际代价 $t$，势能变化 $-t$ → 摊还代价 $= t - t = 0$。
- 结论：所有操作的摊还代价均为 $O(1)$，因此 $n$ 次操作的总实际代价为 $O(n)$。
案例二：二进制计数器加一
- 势能函数：$\Phi(S) =$ 二进制数中 $1$ 的个数。
- 初始状态：$0$，$\Phi = 0$。
- 操作分析：一次加一操作翻转 $t$ 位（末尾连续 $1$ 变为 $0$，再将下一个 $0$ 变为 $1$），实际代价 $t$。势能变化：减少 $(t-1)$ 个 $1$，增加 $1$ 个 $1$，净变化 $2 - t$。摊还代价 $= t + (2 - t) = 2$。
- 结论：每次操作的摊还代价均为 $2$，$n$ 次操作的总实际代价不超过 $2n$，即 $O(n)$。
案例三：动态表插入
- 势能函数：$\Phi(h) = 2n - m$，其中 $n$ 为当前元素个数，$m$ 为表容量。
- 初始状态：空表，$n=0, m=0$，$\Phi = 0$。
- 操作分析：
- 未触发扩容：实际代价 $1$，$n$ 增加 $1$，$m$ 不变，势能增加 $2$ → 摊还代价 $= 1 + 2 = 3$。
- 触发扩容：假设插入前表已满（$m=n$），扩容后 $m' = 2n$，插入后 $n' = n+1$。实际代价 $= n$（复制）$+ 1$（插入）$= n+1$。势能变化：插入前 $\Phi = 2n - n = n$；插入后 $\Phi' = 2(n+1) - 2n = 2$；变化量 $= 2 - n$。摊还代价 $= (n+1) + (2 - n) = 3$。
- 结论：插入操作的摊还代价恒为 $3$，均摊复杂度 $O(1)$。
案例四：动态表的收缩策略（概述）
如果表支持删除操作，当装载因子 $n/m < 1/4$ 时将表容量减半。此时可以定义适当的势能函数（如 $2n - m$ 的变体），使得插入和删除的摊还代价均为常数。具体分析可参考《算法导论》，核心思想仍是让高代价的扩容/收缩操作消耗势能，低代价的普通操作积累势能。
如何自己设计势能函数？
结合以上案例，可以总结出设计势能函数的经验法则：
- 寻找“退化”操作：什么操作会让数据结构变得更“复杂”或更“大”？例如 push 增加栈大小、插入增加表大小。这些操作应该积累势能。
- 寻找“恢复”操作：什么操作会消耗资源并使数据结构简化？例如 multipop、扩容后的复制。这些操作应该消耗势能。
- 确保势能非负且初始为 $0$：这是定理成立的前提。
- 常用势能候选：
- 栈/队列：元素个数。
- 二进制计数器：$1$ 的个数。
- 动态表：$2n - m$（或其变体）。
- 树结构：子树大小的对数和（如 Splay 树）。
- 其他：大于 $1$ 的元素个数、末尾零的个数等。
扩展：势能分析的广泛应用
除了上述例子，势能分析还常用于：
- Splay 树：势能函数为所有子树大小的对数和（$\Phi(S) = \sum_{i=1}^n \log(s_i)$），证明每次操作的摊还代价为 $O(\log n)$。
- 区间开根号：用线段树维护区间最大值，每次递归到叶子修改的有效次数受限于元素值从大变小的次数，通过势能分析可得总复杂度为 $O((n + q) \log n)$。
- 动态表的删除操作：结合扩容与收缩，势能分析可证明所有操作均摊 $O(1)$。
这些应用背后的思想是一致的：将“昂贵”操作的代价分摊到多次“便宜”操作上，从而得到更准确的整体复杂度上界。
注意事项与下一步
- 摊还分析 ≠ 单次操作保证：摊还 $O(1)$ 意味着操作序列的平均代价是 $O(1)$，但某些单次操作仍可能最坏 $O(n)$。在实时系统中，需要考虑最坏情况延迟。
- 验证方法：对于自己设计的势能函数，可以编写小程序模拟操作序列，分别累加实际代价和摊还代价，验证总实际代价是否不超过总摊还代价。
- 下一步：尝试用势能法分析你遇到的其他数据结构，比如并查集的路径压缩、线段树的区间修改等。记住口诀：让消耗大的操作的势能大大的降！