第 4 讲：摊还分析——聚合法、记账法与势能法

一、问题：最坏情况分析太悲观

考虑动态数组（Python 的 list、Java 的 ArrayList、C++ 的 vector）的 push：

type Vector struct {
    data []int // len(data) == size, cap(data) == capacity
}

func (v *Vector) Push(x int) {
    if len(v.data) == cap(v.data) { // 满了
        newCap := max(1, 2*cap(v.data))
        grown := make([]int, len(v.data), newCap)
        copy(grown, v.data) // Θ(n) 拷贝
        v.data = grown
    }
    v.data = append(v.data, x) // Θ(1)
}

Go 的内建 append 自己就实现了这套倍增策略（增长因子随容量在 2 与 1.25 之间变化），这里手写出来是为了看清代价从哪来。

单次 push 最坏是 Θ(n)。那么 n 次 push 是 Θ(n²) 吗？

不是。 因为扩容极其罕见，而且每次扩容后，下一次扩容要等到元素数量再翻倍。n 次 push 的总代价是 Θ(n)，平均每次 Θ(1)。

⭐ 摊还分析（amortized analysis） 就是用来给出这种"一串操作的总代价"的保证的。

摊还代价的定义：若任意 n 个操作的序列总代价为 T(n)，则每个操作的摊还代价为 T(n)/n。

关键性质：这是最坏情况的保证，不含任何概率。 它说的是"无论对手怎么安排操作序列，总代价都不超过这个数"。

二、摊还 ≠ 平均 ≠ 期望

这三个词经常被混用，必须分清：

	随机性来源	保证强度	例子
摊还（amortized）	无随机性	对任意操作序列成立	动态数组 push、并查集
平均情况（average-case）	假设输入服从某分布	分布假设不成立就失效	输入随机时的快排
期望（expected）	算法自己掷硬币	对任意输入成立	随机化快排、跳表

⚠️ 说"动态数组 push 平均是 O(1)“是不准确的，正确说法是"摊还 O(1)"——因为这里根本没有概率，它是一个确定性的最坏情况结论。

⚠️ 另一个重要限制：摊还 O(1) 不代表每次都快。 某一次 push 仍然会花 Θ(n)。对硬实时系统（音频、控制、游戏帧循环），这个尖峰可能是不可接受的，需要改用逐步搬迁（incremental resizing） 把拷贝分摊到每次操作里，换取真正的最坏情况 O(1)。

三、方法一：聚合分析（Aggregate Analysis）

思路：直接算出 n 个操作的总代价 T(n)，然后除以 n。所有操作摊到同一个摊还代价。

例 1：动态数组的倍增扩容

设初始容量 1，n 次 push。扩容发生在第 1, 2, 4, 8, …, 2^k 次 push（2^k ≤ n）时，第 i 次扩容拷贝 2^(i-1) 个元素。

总代价 = n·Θ(1)              （每次 push 的基本写入）
       + Σ_{i=0}^{⌊log₂n⌋} 2ⁱ  （所有扩容的拷贝）
       = n + (2^(⌊log₂n⌋+1) − 1)
       < n + 2n
       = 3n = Θ(n)

每次 push 摊还 Θ(1)。 ∎

⭐ 关键在于几何级数：1 + 2 + 4 + … + n < 2n。扩容代价的总和被最后一次扩容支配，而最后一次只有 Θ(n)。

⚠️ 如果按固定增量扩容会怎样？ 每次容量 +c：

扩容发生在 c, 2c, 3c, … 处，总拷贝 = c + 2c + … + n = Θ(n²/c) = Θ(n²)
⟹ 摊还代价 Θ(n)

这就是为什么所有标准库都用倍增而不是固定增量。 增长因子取 2 还是 1.5 是次要的工程权衡（1.5 更利于内存复用，MSVC 用 1.5，GCC/Clang 用 2），但必须是几何增长。

例 2：二进制计数器递增

k 位计数器从 0 开始，做 n 次 INCREMENT。代价 = 翻转的比特数。

// a[0] 是最低位，返回本次翻转的比特数（即代价）
func Increment(a []byte) int {
    cost, i := 0, 0
    for i < len(a) && a[i] == 1 {
        a[i] = 0 // 把连续的 1 变 0
        i++
        cost++
    }
    if i < len(a) {
        a[i] = 1 // 最低的 0 变 1
        cost++
    }
    return cost
}

单次最坏 Θ(k)（0111…1 → 1000…0）。但看每一位翻转的频率：

位  0:  每 1 次递增翻转一次   →  n     次
位  1:  每 2 次翻转一次       →  n/2   次
位  2:  每 4 次翻转一次       →  n/4   次
位  i:  每 2ⁱ 次翻转一次      →  n/2ⁱ  次
                              ────────────
                       总计 < n·Σ(1/2ⁱ) = 2n

总代价 Θ(n)，摊还每次 Θ(1)。 ∎ 又是几何级数。

四、方法二：记账法（Accounting Method）

思路：给每种操作指定一个摊还代价（可以大于或小于真实代价）。多收的部分作为信用（credit） 存在数据结构的某个对象上，将来给昂贵操作买单。

必须满足的条件：任何时刻，总信用不能为负。

对任意前缀操作序列：Σ 摊还代价 ≥ Σ 真实代价

只有这样，摊还代价才是真实总代价的上界。

例：动态数组

给每次 push 收费 3 元：

1 元  ── 付这次自己写入元素的成本
1 元  ── 存起来，将来搬自己时用
1 元  ── 存起来，将来搬"容量前半段那个没钱的老元素"时用

为什么正好是 3？ 看扩容那一刻：容量从 m 变成 2m 时，需要搬 m 个元素。这 m 个元素中，有 m/2 个是上次扩容之后新加进来的（它们各自存了 2 元），有 m/2 个是更老的（它们的存款已在上次扩容时花光）。新元素的 2m/2 = m 元存款正好覆盖 m 次搬运。✓

摊还代价 = 3 = Θ(1)。 ∎

例：栈的 MULTIPOP

支持三种操作：PUSH（Θ(1)）、POP（Θ(1)）、MULTIPOP(k)（弹出 min(k, size) 个，代价 Θ(min(k,size))）。

单次 MULTIPOP 最坏 Θ(n)。记账法：

操作	真实代价	摊还代价
PUSH	1	2（1 元付压栈，1 元存在这个元素身上）
POP	1	0（用元素自带的存款付）
MULTIPOP(k)	min(k,size)	0（每个被弹元素用自己的存款付）

每个元素最多被弹出一次，而它入栈时已预付了弹出费用。 总信用永不为负 ✓。n 个操作总代价 ≤ 2n = Θ(n)。∎

⭐ 这是摊还分析最核心的直觉：一个元素只能被"处理"有限次，那么就在它进来的时候预付。 这个思路在并查集（第 23 讲）、KMP 的失配指针（第 33 讲）里都会重现。

五、方法三：势能法（Potential Method）

最强大也最常用的方法。思路：定义一个把数据结构状态映射到实数的势能函数（potential function） Φ，它度量"结构中积攒了多少将来要付的债”。

设 D₀ 是初始结构，Dᵢ 是第 i 个操作后的结构，cᵢ 是第 i 个操作的真实代价。定义

摊还代价  ĉᵢ  =  cᵢ  +  Φ(Dᵢ) − Φ(D_{i−1})
                        └──── 势能变化 ────┘

n 个操作的总摊还代价：

Σ ĉᵢ = Σ cᵢ + Φ(Dₙ) − Φ(D₀)          （望远镜求和，中间项全消）

因此，只要保证 Φ(Dₙ) ≥ Φ(D₀)（通常取 Φ(D₀) = 0 且 Φ ≥ 0），就有 Σ ĉᵢ ≥ Σ cᵢ，摊还代价是真实代价的上界。

   代价
    │   真实代价 cᵢ ▄
    │              █           ▄ 势能被消耗（扩容）
    │  ▁▁▁▁▁▁▁▁▁▁▁▁█▁▁▁▁▁▁▁▁  ← 摊还代价 ĉᵢ 保持平稳
    │  ░░░░░░░░░░░░           势能 Φ 缓慢积累
    └────────────────────► 操作序号

例 1：栈的 MULTIPOP

取 Φ(D) = 栈中元素个数。 显然 Φ(D₀) = 0，Φ ≥ 0 ✓。

操作	cᵢ	ΔΦ	ĉᵢ = cᵢ + ΔΦ
PUSH	1	+1	2
POP	1	−1	0
MULTIPOP(k)，弹出 k′ 个	k′	−k′	0

全部 O(1)。∎ 比记账法更机械、更不易出错。

例 2：二进制计数器

取 Φ(D) = 计数器中 1 的个数 bᵢ。

第 i 次 INCREMENT 把 tᵢ 个 1 变成 0，再把 1 个 0 变成 1（若未溢出）：

cᵢ  = tᵢ + 1
ΔΦ = bᵢ − b_{i−1} = (b_{i−1} − tᵢ + 1) − b_{i−1} = 1 − tᵢ
ĉᵢ = (tᵢ + 1) + (1 − tᵢ) = 2 = Θ(1)          ∎

tᵢ 被完美消掉了——这就是好的势能函数的标志。

例 3：动态数组（含收缩）

只考虑扩容时，取 Φ(D) = 2·size − capacity（刚扩容后 size = capacity/2，Φ = 0；填满时 size = capacity，Φ = capacity）。

不触发扩容的 push：c = 1，ΔΦ = 2 ⟹ ĉ = 3。 触发扩容的 push（扩容前 size = capacity = m）：

c  = m + 1                                （拷贝 m 个 + 写入 1 个）
ΔΦ = (2(m+1) − 2m) − (2m − m) = 2 − m
ĉ  = (m + 1) + (2 − m) = 3 = Θ(1)         ∎

⚠️ 收缩策略的陷阱：抖动

如果规定"size 降到 capacity/2 以下就减半容量"，考虑这个操作序列：

数组刚好半满 → push（触发扩容，拷贝 n 个）
             → pop （触发收缩，拷贝 n 个）
             → push（又扩容）→ pop（又收缩）→ …

每次操作都是 Θ(n)，摊还退化成 Θ(n)。 这叫抖动（thrashing）。

正确做法：留出滞后区（hysteresis）——size 降到 capacity/4 才收缩到 capacity/2。这样每次扩容或收缩之后，都需要至少 capacity/4 次操作才能触发下一次，几何级数论证重新成立，摊还回到 Θ(1)。

⭐ 这是本讲最有工程价值的一条结论：任何"自动伸缩"的机制都必须有滞后区，否则会在阈值处抖动。 这条规律同样适用于线程池、连接池、自动扩缩容。

六、三种方法的选择

方法	适用场景	优点	缺点
聚合法	所有操作代价相同、序列结构简单	最直观	不能给不同操作不同摊还代价
记账法	能找到自然的"谁为谁买单"	直觉清晰	需要构造性洞察，易出错
势能法	通用，尤其是复杂结构	机械、可验证、最强	势能函数需要猜

怎么猜势能函数？ 问一句：“结构里现在积攒了多少’将来会很贵’的东西？”

结构	势能函数
栈	元素个数
二进制计数器	1 的个数
动态数组	2·size − capacity
斐波那契堆	树的棵数 + 2×被标记节点数
伸展树（Splay）	Σ log(子树大小)

七、课程中会再遇到摊还分析的地方

讲次	结构	摊还结论
第 5 讲	动态数组	append 摊还 O(1)
第 7 讲	散列表再散列	insert 摊还 O(1)
第 18 讲	B 树	分裂/合并的摊还次数 O(1)
第 23 讲	并查集	每操作摊还 O(α(n))
第 33 讲	KMP	失配指针总移动量 O(n)

随堂自测

用一句话说明"摊还 O(1)“与"平均 O(1)“的区别。哪一个不依赖任何假设？
若动态数组每次扩容 +100 个位置（而非翻倍），n 次 append 的总代价是多少？摊还代价呢？
用势能法证明：栈操作序列（PUSH/POP/MULTIPOP）中每个操作摊还 O(1)。写出你的 Φ 并验证 Φ ≥ 0。
一个 k 位二进制计数器同时支持 INCREMENT 和 DECREMENT。证明摊还代价不再是 O(1)，给出一个使摊还退化为 Θ(k) 的操作序列。
为什么动态数组的收缩阈值取 capacity/4 而不是 capacity/2？构造 capacity/2 时的最坏序列。
某结构的操作序列中，每 √n 次操作会有一次 Θ(n) 的重建，其余操作 Θ(1)。摊还代价是多少？
“摊还 O(1) 意味着不会有卡顿”——这句话对吗？在什么场景下它会造成实际问题，怎么办？

一、问题：最坏情况分析太悲观#

二、摊还 ≠ 平均 ≠ 期望#

三、方法一：聚合分析（Aggregate Analysis）#

例 1：动态数组的倍增扩容#

例 2：二进制计数器递增#

四、方法二：记账法（Accounting Method）#

例：动态数组#

例：栈的 MULTIPOP#

五、方法三：势能法（Potential Method）#

例 1：栈的 MULTIPOP#

例 2：二进制计数器#

例 3：动态数组（含收缩）#

⚠️ 收缩策略的陷阱：抖动#

六、三种方法的选择#

七、课程中会再遇到摊还分析的地方#

随堂自测#