均摊分析、最坏与期望复杂度

一句话定义

均摊分析（Amortized Analysis）把操作序列中偶发的昂贵代价摊到整个序列上，给出「每操作的长期平均上界」；它与最坏复杂度（单次操作保证）和期望复杂度（对随机性的平均）是三种不同口径，混用会导致对系统行为（尤其尾部延迟）的误判。

为什么重要

动态数组、哈希表、Splay 树的每次操作单独看都可能是昂贵的（扩容、rehash、旋转），但真实系统关心的是吞吐与总耗时，这必须由均摊口径回答；而实时系统关心单次最坏延迟，又必须回到最坏口径。能区分这三种口径，才算真正读懂了任何结构文档里那句「O(1) 插入」。

前置知识

kp-002（渐进记号）；对「操作序列」而非单次操作建模的意识。

核心概念

• 最坏（Worst-case）：任意输入、任意时刻的单次操作上界，是唯一能做硬保证的口径。
• 期望（Expected）：算法含随机性（如随机 pivot）或输入符合概率模型时，代价的数学期望；期望 O(1) 不排除单次 O(n)。
• 均摊（Amortized）：确定性序列上的总代价除以操作数；不依赖概率，是对「长期平均」的严格上界。
• 三种证明技法：聚合法（求和再除）、记账法（给便宜操作预存费用）、势能法（定义势函数 Φ，实际代价+ΔΦ 的摊还代价恒非负）。
• 典型对象：动态数组倍增扩容、哈希表 rehash、二进制计数器、两栈实现队列。

原理与机制

三种均摊技法共享同一内核——「让昂贵操作被一串便宜操作供养」：聚合法直接对操作序列求和再除以长度；记账法给便宜操作预收费用存入账户，昂贵操作从账户支取，要求任意时刻余额非负；势能法把账户余额形式化为势函数 Φ，定义摊还代价 = 实际代价 + ΔΦ，对全序列求和后首尾势能相消，总额仍封住实际总代价。动态数组的几何级数求和就是最简的实例。

直观类比

自助餐厅大桶换桶：平时盛汤零成本，桶空了换新桶要等 2 分钟。你不会说「盛一次汤最坏 2 分钟」吓跑客人，而是说「平均盛一次几乎免费」——前提是换桶次数被桶容量摊薄。但如果你做的是「每勺都必须 1 秒内」的流水线，就必须为换桶瞬间单独设计预案（最坏口径）。

公式或模型

动态数组倍增（容量不足时翻倍）的均摊 O(1) 证明（聚合法）：

从空表起连续插入 n 次，触发的搬家代价：
2 + 4 + 8 + … + 2^⌈log₂n⌉  ≤  2n
总代价 ≤ n（每次插入本身） + 2n（搬家） = 3n
⇒ 均摊每插入一次 O(1)，虽然触发搬家那一次是 Θ(n)。

关键在于几何级数求和被 2n 封顶——这正是「必须按倍数增长、不能按固定增量增长」的原因：若每次只扩容 +c，则搬家常发，总代价退化为 Θ(n²/c)。

图示

插入次数:  1  2  3  4  5  6  7  8  9 … 16 17
容量:      1  2  2  4  4  4  4  8 … 16 16→32
单次代价:  1  2  1  4  1  1  1  8 … 16 17
              ↑       ↑           ↑    ↑
            搬家贵，但被之前的免费操作摊平 → 均摊 O(1)

实例或案例

• C++ vector / Python list / Java ArrayList 都是倍增（增长因子约 1.5–2），均摊尾插 O(1)；工程上可 reserve 预分配来消除扩容尖峰。
• 哈希表在负载因子超阈值时 rehash 整表，单次 O(n)、均摊 O(1)（见 kp-009）。
• 两栈实现队列：dequeue 最坏 O(n)（倒栈），均摊 O(1)——每个元素一生最多被倒两次。
• 二进制计数器 increment：最坏翻转 Θ(log n) 位，均摊 O(1)（势能法经典例）。

常见误区

• 混淆均摊与期望：均摊是确定性结论，期望依赖概率模型；两者都允许单次操作很贵。
• 拿均摊 O(1) 向实时系统承诺延迟：扩容那一次的 Θ(n) 停顿在 P99.9 上是真实存在的，需预分配或增量扩容。
• 扩容因子乱选：因子太大浪费内存且单次搬家更久，太小（如 +1）则均摊退化；工程取 1.5–2。
• 认为均摊下界不重要：如果某操作序列总代价就是 Θ(n²)，任何「平均很便宜」的说法都是错的。

自测题

1. 用记账法重证动态数组倍增插入均摊 O(1)。

答案要点：每次插入收 3 元（1 元自用，1 元付自己将来被搬家，1 元付已搬一半的旧元素搬家），任意时刻存款非负且总花费 ≤ 3n。

1. 哈希表 rehash 为什么也是均摊 O(1)？前提条件是什么？

答案要点：容量与元素数成比例地翻倍，两次 rehash 之间插入 Ω(m) 个元素，摊平 O(m) 搬迁；前提是按负载因子触发、容量倍增。

1. 若某哈希表每次只扩容 +10 桶，长期插入的均摊复杂度变成什么？

答案要点：rehash 间隔只增 10 桶，总搬迁代价 Θ(n²/10) ⇒ 均摊 Θ(n)，退化为线性。

与其他知识点的关系

kp-006（动态数组）、kp-009（哈希表）是本节两大落地对象；kp-013 红黑树、kp-030 并查集的分析也依赖均摊/势能思想；kp-032 提醒工程中如何把「均摊尖峰」用预分配消除。

延伸阅读

《算法导论》第 17 章「摊还分析」（聚合、记账、势能三法与动态表一节）。