【算法分析与设计】第9篇：平摊分析与聚合核算技术
我们通常分析算法复杂度时，习惯盯着最坏情况——一次操作在最倒霉的输入下会消耗多少资源。这个指标给出了安全的性能下限，但有时过于保守，甚至会误导我们对数据结构实用性的判断。
考虑一个简单的例子：从一个空栈开始，连续执行n次操作，每次要么是push（压入），要么是multipop(k)（弹出k个元素）。multipop的最坏情况代价是O(n)，如果n次操作全都是multipop，总代价似乎是O(n²)。但这不可能发生——因为multipop能弹出的元素不能超过此前push进去的数量。直觉告诉我们，n次操作的总代价应该只是O(n)。平摊分析要做的，就是把这种直觉转化为严格的数学论证。
一、平摊分析与平均情况分析的区别
在引入具体方法前，必须厘清一个常见的概念混淆。平均情况分析是对输入的概率分布求期望，需要假设输入的统计特征，算法本身可能包含随机性，最终给出的是期望运行时间。而平摊分析是确定性的——它不考虑输入分布，只对任意操作序列求平均，是对最坏情况序列的“均摊”。平摊分析保证的是：对任意长度为n的操作序列，总代价不会超过n乘以平摊代价。这是一种无条件的、确定性的上界。
二、聚合分析法
聚合分析是最直观的一种平摊分析技术。思路很简单：直接分析n次操作的总代价T(n)，然后令每次操作的平摊代价为T(n)/n。
仍以栈操作为例。在一个空栈上执行n次push和multipop的任意交错序列。每个元素至多被push一次、被pop一次（无论是普通pop还是multipop中的弹出）。因此n次操作中，pop操作的总次数不可能超过push的总次数，而push的总次数不超过n。每次push和pop的实际代价均为O(1)，故T(n)=O(n)，每次操作平摊代价为O(1)。
聚合分析简单粗暴，但它的局限也很明显：它对所有操作给出相同的平摊代价，无法区分不同类型操作的不同贡献。当数据结构有多种操作混合时，我们往往需要更精细的工具。
三、记账法
记账法引入了一种“会计”视角：我们为每种操作预设一个平摊代价，当平摊代价高于实际代价时，差额作为“信用”存入数据结构中；当实际代价高于平摊代价时，从之前的信用中支取以填补差额。关键约束是：在任意时刻，数据结构的信用总额必须非负。这就保证了对于n次操作，∑平摊代价i≥∑实际代价i∑平摊代价i≥∑实际代价i。
以栈操作为例。设push的平摊代价为2，其中1用于支付压入操作本身，另1作为信用存入；pop和multipop的平摊代价设为0，其实际代价从已有信用中扣除。每次pop一个元素消耗1单位信用，恰好由该元素被push时存入的信用支付。因此信用始终非负，n次操作的平摊代价总和至多为2n，每次O(1)。
记账法的优势在于灵活——我们可以为不同操作分配不同的平摊代价，只要信用约束成立，结论便成立。
四、势能法
势能法是用物理学类比来统一处理平摊分析。定义数据结构的一个势函数Φ(Di)Φ(Di)，将数据结构在操作i之后的状态 DiDi 映射为一个实数，视作该状态的“势能”。第i次操作的平摊代价定义为：
c^i=ci+Φ(Di)−Φ(Di−1)c^i=ci+Φ(Di)−Φ(Di−1)
其中 cici 为实际代价。将n次操作的平摊代价累加，势能项前后抵消，得到 ∑c^i=∑ci+Φ(Dn)−Φ(D0)∑c^i=∑ci+Φ(Dn)−Φ(D0)。若我们选取势函数满足 Φ(Dn)≥Φ(D0)Φ(Dn)≥Φ(D0)（通常令 Φ(D0)=0Φ(D0)=0 且势函数始终非负），则有 ∑c^i≥∑ci∑c^i≥∑ci，平摊代价总和构成实际总代价的上界。
势能法的核心技巧在于势函数的构造。一个好的势函数应该使低代价操作的势能略微上升（储蓄能量），高代价操作的势能大幅下降（释放能量），从而使各操作的平摊代价趋于均衡。
五、案例演示：动态表扩容
假设我们用数组实现一个动态表，初始容量为1。当数组满时，插入操作触发扩容：分配一个大小为原来两倍的新数组，将旧元素全部拷贝过去，再插入新元素。单次扩容的代价是O(n)，但显然n次插入的总代价不可能达到O(n²)。我们来用三种方法分析。
聚合分析：设 cici 为第i次插入的代价。若i-1恰为2的幂，则 ci=ici=i（扩容拷贝i-1个元素再加插入）；否则 ci=1ci=1。总代价为：
T(n)=∑i=1nci≤n+∑j=0⌊logn⌋2j<n+2n=3n=O(n)T(n)=∑i=1nci≤n+∑j=0⌊logn⌋2j<n+2n=3n=O(n)
记账法：令每次插入的平摊代价为3。其中1支付本次插入，1存入该元素（用于未来它被拷贝时支付开销），1存入旧表中某个尚未被分配信用的元素。分析可得信用始终非负，总平摊代价3n。
势能法：定义 Φ(Di)=2×(当前元素数)−(当前容量)Φ(Di)=2×(当前元素数)−(当前容量)。设第i次插入前的元素数为 si−1si−1，容量为 capi−1capi−1。若不触发扩容，实际代价为1，势函数增量为 2×1−0=22×1−0=2，平摊代价 c^i=1+2=3c^i=1+2=3。若触发扩容，capi−1=si−1capi−1=si−1，扩容后容量翻倍。实际代价为 si−1+1si−1+1，势函数从 2si−1−si−1=si−12si−1−si−1=si−1 变为 2(si−1+1)−2si−1=22(si−1+1)−2si−1=2，势能变化为 2−si−12−si−1。平摊代价 c^i=(si−1+1)+(2−si−1)=3c^i=(si−1+1)+(2−si−1)=3。在所有情况下平摊代价均为O(1)。
三种方法殊途同归。聚合分析最为直观，记账法适合操作类型多变的场景，势能法最为通用且形式优美，是算法竞赛和理论论文中的主流工具。
平摊分析本身不设计新算法，但它赋予了我们对效率更精细的洞察力。下一篇，我们将把视角从算法效率的分析方法，转向问题本身固有难度的探索——下界理论与NP完全性初步。