摊还分析入门

一句话

单次操作代价巨大不代表整体慢——只要"贵"的次数被"便宜"的次数均摊过来，平均仍可控。摊还分析就是把这种"凭直觉"的统计变成形式证明。它是后面所有动态数组、并查集、Splay 树、Bloom 滤波等结构的工程性能证明语言。

为什么不能用纯最坏复杂度

考虑动态数组的 push_back：

大部分时间是 O(1)（写入下一空槽）；
满了就要扩容 O(n)：申请新数组、拷贝 n 个元素、释放旧数组。

如果你只看"最坏"，会得到 push 是 O(n)。代入 N 次 push 的和：O(N · n) = O(N²)。但直觉告诉我们 N 次 push 在 Θ(N) 量级。证明需要等会一种"统计序列"的工具——摊还分析。

之所以这件事重要，是因为工程上你几乎从不在 N 次 push 都打到 O(n) 最坏。但你要证明这一点，需要把"实际代价序列求和除以操作数"写成一个数学上可证的程序。

三种方法

1. 聚集法（Aggregate）：先求全部，再除以次数

最朴素做法：把所有 n 次操作的总代价求和，再除以 n。

动态数组倍增继续上节的节奏：

扩容发生在 size=1, 2, 4, 8, …
每次扩容的开销 = 旧 size（拷贝）+ 1（写新元素）
总开销 = 1 + (1+2) + (1+4) + (1+8) + … + (1+n/2)
       ≈ n + n/2 + n/4 + … 
       = 2n ≈ 2n
加上每次 push 本身的 1 次 write：+ n
总和 ≈ 3n。
摊还到每次：Θ(1)。

简单，但不能精细区分每个操作的代价。

2. 会计法（Banker）：给便宜操作"预存"，贵的时候花

给每次便宜操作多记一点当信用：

push 实际花 1，记账 3；
多余 2 进账户；
当扩容发生，n 个元素搬迁要花 n，正好从账户里掏（账户此时余额 ≥ 2·(n/2) = n）。

账户永不为负 ⇒ 每次操作实际累计 ≤ 记账累计 = 3n ⇒ 摊还 O(1)。

tip

会计法的好处：能给不同操作不同代价预算。后面的并查集、链表反转都能用，而且比聚集法精细。

3. 势能法（Potential）：物理直觉的可迁移方法

定义势能函数 Φ(i) = Φ(D_i)，描述第 i 次操作后的"数据结构能量". 要求：

Φ(0) = 0；
对所有 i ≥ 0，Φ(i) ≥ 0.

定义第 i 次操作的摊还代价：

a_i = c_i + Φ(D_i) − Φ(D_{i-1})

求和：

Σ a_i = Σ c_i + Φ(D_n) − Φ(0)
       ≥ Σ c_i        （因为 Φ(D_n) ≥ 0 = Φ(0)）

也就是说如果你能给所有 a_i 一个上界 k，那 Σc_i ≤ k·n. 这是最有工程性、最可移植的方法。记住势能法，所有结构摊还证明你都能用.

用势能法重证动态数组 O(1) 摊还

先试一个朴素势能：Φ(i) = 2·i − cap_i，其中 i 是当前元素数、cap_i 是容量。

普通 push 不触发扩容：实际 1，ΔΦ = 2，摊还 3. OK.
触发扩容 push：扩容前 cap = i-1，即"之前刚好满 i-1 个的位置再加一个". 实际开销 = i (拷贝旧 i-1 个 + 写新元素).

按上面 Φ(i-1) = 2(i-1) − cap_{i-1}，cap_{i-1} 在扩容前 = i-1 ⇒ Φ(i-1) = i-2. 扩容后 cap = 2·cap_old = 2(i-1)，新 i 个元素 ⇒ Φ(i) = 2i − 2(i-1) = 2. ΔΦ = 2 − (i-2) = 4 − i.

摊还 = i + (4 − i) = 4. 这跟上面普通情形的 3 不匹配，但仍为常数。所以两种情形都是常数 ⇒ 每次插入摊还 O(1)，比例常数 4.

note

在势能法里，定义一个新势能函数的"调参"环节通常要试 2-3 次。一旦找到合适的势能函数，结果立刻便宜十倍。这是数学工程的味道。

经典案例速查 + 直觉

结构	实际最坏	摊还	势能常见定义
动态数组 push	Θ(n)	Θ(1)	`2i − cap`
二进制计数器 +1	Θ(k) bit 翻	Θ(1)	`#1-bits`
Splay 树操作	Θ(n)	Θ(log n)	`Σ log(size(v))`
并查集 find（路径压缩 + 按秩）	Θ(α(n)) 极慢反例	实际 ~4 ops	联集势能（计分函数）
哈希表 rehash	Θ(n)	Θ(1)	装填因子的惩罚

二进制计数器是一个非常直观的势能法例子：n 次 +1 中，最低位每两次翻一次（n/2 次），第二位每四次（n/4 次）……总位数翻转 = n/2 + n/4 + … = O(n) ⇒ 每次摊还 O(1). 你甚至能看到"低位翻得多、高位翻得少"的频次，这就是势能法的心脏直觉。

Splay 树：势能法处理的关键案例

Splay 树没有显式平衡。当访问一个节点 x 时，会通过 zig/zig-zig/zig-zag 把它旋转到根。单次最坏 O(n)。但势能法证明：

定义 Φ(D) = Σ_v log(size(v))，并证明任何操作摊还 O(log n). 核心是 zig/zig-zig 的几何效应：每次 splay 操作都会把访问路径上"重子树 → 轻子树"翻转一次，这种翻转产生势能释放直接抵掉操作的代价。

工程含义：访问过的 key 会被旋转到根，采样命中率高时变成"自适应 cache" —— 这就是 Splay 在 Windows 内核里被 Linux CFS 替代前用过一阵的原因。

并查集摊还 = 反阿克曼

只要按秩合并（rank merge）+ 路径压缩，第 n 次 find 的摊还 = O(α(n))，其中 α 是 逆 Ackermann 函数——n ≤ 10⁸⁰ 时 α(n) ≤ 4。实际操作几乎常数。

证明思路非常深（Tarjan 1975），需要：

把每个节点按 rank 分块；
在每块内分析 find "跨块"的次数；
推跨块的多项式级数。

要在工程里读这个证明很累，但结论一句话：并查集的每次操作 ≈ 4 条指令的真实代价——比平衡树 find 小得多。

工程视角：摊还分析的两个不适用区

硬实时系统。摊还 O(1) 的意思是"长序列平均 O(1)"，并不保证每次都 O(1). 反例：动态数组在第 2^23 个 push 触发扩容，最坏延迟可能数 ms（如果页耗尽需要 syscall 触发 mmap/munmap —— 让 hypervisor 介入甚至给物理页做 numa 分配），HFT/游戏 tick 容不下这种尖刺。

解法：
- 启动时 reserve(max)；
- 或换固定容量的 ring buffer；
- 或换 incremental rehash（dictugador 风格，把扩容代价分摊到多次 op）。
失败重试场景。如果 N 次 push 里中间某次扩容由于 OOM 而失败，整个数据结构状态可能不一致了。这是 C++ std::vector::push_back 强 EH 保证要求的根源：扩容用临时节点 + commit，不破坏原数据。

这一章带走的东西

平均 vs 摊还 vs 最坏三个量级，和实际系统行为不能直接对调；
势能法是"工程化"的摊还分析，学会就解锁了一切摊还结构；
动态数组的常数是 3，不是抽象的 1；
Splay 树、并查集、rehash、二进制计数器都靠"势能爆发"在 O(1) 里隐藏 O(n) 的烧火；
当心两种工程坑：硬实时系统的尖刺、失败回滚下的结构一致性。

下一节 → 实战：复杂度反推设计：把 O(·) 从理论用到工程约束反推。

Keyboard shortcuts

Computer Science Notes