我们通常分析算法复杂度时习惯盯着最坏情况——一次操作在最倒霉的输入下会消耗多少资源。这个指标给出了安全的性能下限但有时过于保守甚至会误导我们对数据结构实用性的判断。考虑一个简单的例子从一个空栈开始连续执行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^iciΦ(Di)−Φ(Di−1)c^iciΦ(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的幂则 ciicii扩容拷贝i-1个元素再加插入否则 ci1ci1。总代价为T(n)∑i1nci≤n∑j0⌊logn⌋2jn2n3nO(n)T(n)∑i1nci≤n∑j0⌊logn⌋2jn2n3nO(n)记账法令每次插入的平摊代价为3。其中1支付本次插入1存入该元素用于未来它被拷贝时支付开销1存入旧表中某个尚未被分配信用的元素。分析可得信用始终非负总平摊代价3n。势能法定义 Φ(Di)2×(当前元素数)−(当前容量)Φ(Di)2×(当前元素数)−(当前容量)。设第i次插入前的元素数为 si−1si−1容量为 capi−1capi−1。若不触发扩容实际代价为1势函数增量为 2×1−022×1−02平摊代价 c^i123c^i123。若触发扩容capi−1si−1capi−1si−1扩容后容量翻倍。实际代价为 si−11si−11势函数从 2si−1−si−1si−12si−1−si−1si−1 变为 2(si−11)−2si−122(si−11)−2si−12势能变化为 2−si−12−si−1。平摊代价 c^i(si−11)(2−si−1)3c^i(si−11)(2−si−1)3。在所有情况下平摊代价均为O(1)。三种方法殊途同归。聚合分析最为直观记账法适合操作类型多变的场景势能法最为通用且形式优美是算法竞赛和理论论文中的主流工具。平摊分析本身不设计新算法但它赋予了我们对效率更精细的洞察力。下一篇我们将把视角从算法效率的分析方法转向问题本身固有难度的探索——下界理论与NP完全性初步。
