第 17 章摊还分析 (Amortized Analysis)

核心结论

摊还分析定义：在操作序列上平均计算每步成本；不依赖概率，担保最坏情况下的平均性能——单步昂贵操作由未来便宜操作「分摊」。
三种方法：聚合分析 (aggregate) 给所有操作同一摊还成本；记账法 (accounting) 给不同操作不同摊还成本并维护「信用」；势能法 (potential) 用势函数 χ(D_i) 描述数据结构状态、本次摊还成本 = 实际成本 + 势差。
栈与 MULTIPOP：n 次 PUSH/POP/MULTIPOP 摊还成本 O(1)，单次 MULTIPOP 仍可能 O(n)。
二进制计数器：n 次 INCREMENT 摊还 O(1)，最坏单次 Θ(k) 但每 bit 翻转次数 ≤ ⌊n/2^i⌋ 之和 < 2n。
动态表扩张/收缩：TABLE-INSERT 与 TABLE-DELETE 摊还 O(1)；势函数 χ = 2·num − size（扩缩时为 0）。load factor 始终 ≥ 1/2（扩张后容量翻倍 + 收缩阈值 1/4）+ 关键。

本章主旨

本章建立三种摊还分析的工具箱（聚合 / 记账 / 势能），同一组示例（栈、MULTIPOP、二进制计数器、动态表）反复练习直到直觉建立。第 17.4 节的动态表是最实用的应用——它展示了「势函数设计」的精妙：扩张时 χ=0、装满后 χ=num，扩缩时机由 χ 控制。本章与第 16 章贪心并列——前者处理「设计上均摊」，后者处理「选择上贪心」；两者都是算法设计中「跨越最坏分析」的核心技巧。

一、核心概念

本章围绕 5 个核心概念展开：先建立三种摊还方法的定义与公理（17.1-17.3），再用同一示例对比，再深入到动态表（17.4）的工程实践。

概念	定义 + 重要性	实现提示
聚合分析 (Aggregate)	n 步总成本 ≤ T(n)，摊还成本 = T(n)/n；不区分操作类型，最简单。	§17.1；二进制计数器总代价 ≤ 2n（每 bit 翻转次数 Σ⌊n/2^i⌋ < n·Σ 1/2^i < 2n）。
记账法 (Accounting)	给每操作分配摊还成本 c_i，多出部分作为「信用」存于对象；信用 ≥ 0 是分析正确的关键。	§17.2 PUSH 收费 2、自身用 1、放 1 在栈对象上供 POP 用；MULTIPOP 收费 0。
势能法 (Potential)	势函数 χ: 数据结构 → ℝ，摊还成本 = c_i + χ(D_i) − χ(D_{i-1})；χ(D_n) ≥ χ(D_0) 时摊还和 ≥ 实际和。	§17.3 通用框架；栈 χ = 栈大小，INCREMENT χ = 1 的个数，二进制表 χ = 2·num−size。
动态表扩张 (Table Expansion)	表满时分配 2 倍容量的新表并复制 → 单次 O(n)；用 χ = 2·num − size 平均后摊还 O(1)。	§17.4.1 TABLE-INSERT 伪代码 (lines 1-11);扩张当 num+1 > size;Copy i 个元素，cost = i。
动态表扩张 + 收缩	同时处理扩缩，避免「插入-删除震荡」（insert/delete 序列反复 trigger resize）造成摊还成本爆炸。	§17.4.2;收缩阈值 1/4 满 + 删除前预定：势能 χ = 2·num − size (num ≤ size/2) 或 size − 2·num (num > size/2)，仍摊还 O(1)。

概念

定义 + 重要性

实现提示

聚合分析 (Aggregate)

n 步总成本 ≤ T(n)，摊还成本 = T(n)/n；不区分操作类型，最简单。

§17.1；二进制计数器总代价 ≤ 2n（每 bit 翻转次数 Σ⌊n/2^i⌋ < n·Σ 1/2^i < 2n）。

记账法 (Accounting)

给每操作分配摊还成本 c_i，多出部分作为「信用」存于对象；信用 ≥ 0 是分析正确的关键。

§17.2 PUSH 收费 2、自身用 1、放 1 在栈对象上供 POP 用；MULTIPOP 收费 0。

势能法 (Potential)

势函数 χ: 数据结构 → ℝ，摊还成本 = c_i + χ(D_i) − χ(D_{i-1})；χ(D_n) ≥ χ(D_0) 时摊还和 ≥ 实际和。

§17.3 通用框架；栈 χ = 栈大小，INCREMENT χ = 1 的个数，二进制表 χ = 2·num−size。

动态表扩张 (Table Expansion)

表满时分配 2 倍容量的新表并复制 → 单次 O(n)；用 χ = 2·num − size 平均后摊还 O(1)。

§17.4.1 TABLE-INSERT 伪代码 (lines 1-11);扩张当 num+1 > size;Copy i 个元素，cost = i。

动态表扩张 + 收缩

同时处理扩缩，避免「插入-删除震荡」（insert/delete 序列反复 trigger resize）造成摊还成本爆炸。

§17.4.2;收缩阈值 1/4 满 + 删除前预定：势能 χ = 2·num − size (num ≤ size/2) 或 size − 2·num (num > size/2)，仍摊还 O(1)。

二、详细笔记

2.1 聚合分析

What：对所有 n 个操作求总代价上界 T(n)，摊还成本 = T(n) / n（所有操作取同一值）。

Why：最简单的摊还方法。当所有操作摊还成本一样时它最直接——既不用设计势函数也不用维护信用。

How：

STACK 示例：n 次 PUSH / POP / MULTIPOP 总代价 ≤ 2n（每个对象至多 push 1 次 + pop 1 次），摊还 O(1)。
二进制计数器 INCREMENT：A[0] 每次翻、A[1] 每 2 次翻、A[2] 每 4 次翻……总翻转次数

\[\sum_{i=0}^{k-1} \left\lfloor \frac{n}{2^i} \right\rfloor < n \cdot \sum_{i=0}^{\infty} \frac{1}{2^i} = 2n \qquad (17.1 \text{ 配合 })\]

摊还成本 ≤ 2。

When：当操作类型 ≤ 2 种，或所有操作成本大致相同时优先使用。

Example：multi-pop 栈中每次 pop 必须对应至少一次 push（从空栈 pop 报错），故总 pop ≤ push ≤ n；总成本 ≤ 2n。

2.2 记账法

What：给每类操作指定不同摊还成本 c_i；操作超额缴费时把差额作为「信用」存在对象上；未来操作「欠费」时用信用补——全程信用 ≥ 0 是前提。

Why：比聚合分析更细——可让便宜的操作收费更少，让昂贵的操作提前预支；与势能法等价但「信用」依附于具体对象（更直观）。

How：

操作	实际成本	摊还成本
逻辑	PUSH	1
2	1 自身用 + 1 留在对象供 POP	POP
1	0	用 PUSH 留在对象上的 1
MULTIPOP	min(k,s)	0
每 pop 用对象的 1	计数器置 1	1
2	1 置位 + 1 留给清 0	计数器清 0
1	0	用置位的 1

When：操作成本异质（不同操作实际成本差异大），且可对应到具体对象时用记账法——信用可在对象之间清晰流转。

Example：记账法下 PUSH 收费 2、POP 收费 0、MULTIPOP 收费 0；每次 PUSH 多交的 1 一直「跟着」该对象直到它被 pop。

2.3 势能法

What：势函数 χ 把数据结构映射到实数；第 i 步摊还成本 \(\hat{c_i} = c_i + \Phi(D_i) - \Phi(D_{i-1})\)；要求 \(\Phi(D_n) \geq \Phi(D_0)\) 即总摊还 ≥ 总实际。

Why：势能法最通用——势函数聚焦「数据结构状态」而非单个对象；很多问题（如动态表）势能设计比记账法更自然。

How：

\[\sum_{i=1}^{n} \hat{c}_i = \sum_{i=1}^{n} c_i + \Phi(D_n) - \Phi(D_0) \geq \sum c_i \qquad (17.3)\]

STACK：χ = 栈大小 → PUSH 摊还 2（cost 1 + 势 +1）；MULTIPOP 摊还 0（cost k′ − 势 k′）。
二进制计数器：χ = 1 的个数 → INCREMENT 摊还 ≤ 2（cost 1 + 势 ≤ 0 + 1）。
部分和：χ(D_n) − χ(D_0) 给出「免费尾款」，可校准初始值以更紧（式 17.4）。

When：势能法几乎通用——只要能定义一个总势能递增（或非负）的势函数。其相对于记账法的优势：势只属于数据结构而非元素，便于动态缩扩。

Example：计数器初始 b₀ 个 1、终止 bₙ 个 1、n 次 INCREMENT，由 (17.4) 得

\[\sum c_i \leq 2n - b_n + b_0 \leq 2n + k \qquad (\text{若 } b_0 \leq k, n = \Omega(k))\]

即从任意初值起，「n ≥ Ω(k)」次 INCREMENT 总代价 O(n)。

2.4 动态表扩张 (Table Expansion)

What：TABLE-INSERT 在「表满」（num+1 > size）时分配 size' = 2·size 的新表，复制所有元素到新表，再插入新元素——单次 O(size)，但摊还 O(1)。

Why：动态表是「按需扩容」的经典实现——避免事先估计容量造成空间浪费；通过势能分析得到「平均每次插入 O(1)」的严格上界。

How：

势 χ	触发条件
摊还成本	2·num − size
num < size/2（不触发）	TABLE-INSERT 摊还 ≤ 3
size − 2·num	num < size/2（删除触发）

势 χ

触发条件

摊还成本

2·num − size

num < size/2（不触发）

TABLE-INSERT 摊还 ≤ 3

size − 2·num

num < size/2（删除触发）

扩缩临界：TABLE-INSERT 在 num+1 > size 时触发；TABLE-DELETE 在 num < size/4 时触发（避免删 1 个就缩），配合 χ 双段定义。

When：任何「容量预分配 + 复制扩容」场景（哈希表、向量、文件缓冲区等）皆可用此分析模板。

Example：表从空开始连续 8 次插入，size ∈ {1,2,4,8,16}：实际总成本 = 1+2+1+4+1+2+1+1 = 13；摊还成本 = 3·8 = 24 > 13 ✓。

2.5 动态表扩张 + 收缩

What：同时支持插入与删除时，简单「满则翻倍、空则减半」会因「delete/insert 交替」反复触发 resize 导致摊还成本爆炸；CLRS 用「双重阈值」+ 两段势函数解决。

Why：仅扩张（17.4.1）可删元素但缩表策略不可；本节给出完整动态表的严格 O(1) 摊还分析——是工程实践中「哈希表 resize」的精确刻画。

How：

收缩阈值：num < size/4 时缩为 size/2（不是 size/2 临界，是 size/4）；避免 1 次删除紧接 1 次插入就触发一轮 resize。
势函数双段：

\[\Phi(T) = \begin{cases} 2 \cdot \text{num} - \text{size} & \text{if } \text{num} \leq \text{size}/2 \\ \text{size} / 2 - \text{num} & \text{if } \text{num} > \text{size}/2 \end{cases}\]

TABLE-INSERT 摊还成本上界 = 3；TABLE-DELETE 摊还成本上界 = ？（CLRS 习题 17.4-3 推导 ≤ 3）。
load factor 始终 ≥ 1/2 减一个常数；浪费空间 ≤ 一半。

When：完整的动态集合（哈希表、内存分配器 slab、操作系统页缓存）需要扩+缩时使用此模式。

Example：n 次 insert + n 次 delete 交替 → 简单「装满翻倍、空则减半」会让每次操作都触发 resize，摊还成本 Θ(n)；改用「size/4 才减半」+ 两段势能 → 摊还 O(1)。

三、关键图表

核心公式对照表

公式

含义

式 17.1

记账法不变量：Σ c_i ≤ Σ ĉ_i ↔ 信用 ≥ 0

式 17.2

势能定义：ĉ_i = c_i + Φ(D_i) − Φ(D_{i−1})

式 17.3

势能累加：Σ ĉ_i = Σ c_i + Φ(D_n) − Φ(D_0)

式 17.4

重写为 Σ c_i = Σ ĉ_i − Φ(D_n) + Φ(D_0)，便于紧界分析

二进制计数器

bit i 翻转 ≤ ⌊n/2^i⌋，总和 < 2n

动态表

χ = 2·num − size，扩后 χ=0，满前 χ=num

四、思维导图

mindmap
  root((第 17 章 摊还分析))
    聚合分析
      总价T(n)/n
      二进制计数器
      MULTIPOP栈
    记账法
      信用预付
      PUSH=2/POP=0
      对象上存储信用
    势能法
      Φ映射数据结构
      摊还=实际+势差
      Φ终值≥初值
    通用不变量
      信用/势≥0
      摊还和≥实际和
    栈操作
      Φ=栈大小
      PUSH=2/POP=0
    计数器
      Φ=1的个数
      INCREMENT≤2
    动态表扩张
      满则翻倍
      Φ=2num-size
      摊还≤3
    动态表扩缩
      缩阈值size/4
      两段势能
      摊还O1

五、重点与易错点

三种方法等价但表达不同：聚合最简单、记账最直观、势能最通用——同一问题可用任一种，关键是「总摊还 ≥ 总实际」。
「摊还成本」与「平摊运行时间」不是一回事——它是「分配给每步的虚拟成本」，不一定等于该步的实际机器时间。
势能法核心不变量：Φ(D_n) − Φ(D_0) ≥ 0；常设 Φ(D_0) = 0 并证 Φ(D_i) ≥ 0 对所有 i 即可。
INCREMENT 的 cost 用「bit 翻转数」度量（CLRS 简化）；若按 CPU 时间则更复杂，但摊还结论仍类似。
动态表收缩阈值不是 size/2 而是 size/4——CLRS 用 size/4 是为了避免「删除-插入震荡」造成的摊还爆炸；改 size/2 反而失败（习题 17.4-3）。
记账法中「信用 ≥ 0」是绝对前提——若允许负信用，则摊还和可能低于实际和，分析失效。
第 17 章未涉及「加权势能」或「随机摊还」（如 skip list 的预期摊还）；它们在第 18 章后的数据结构中常出现。
势能 vs. 记账：势能是「数据结构级」的，记账是「元素级」的——前者改 χ 即可重新设计，后者要逐元素调整。
摊还下界可用「构造性下界」证明：构造一组操作序列迫使成本集中在某步——最坏摊还成本是 hard 指标（如动态表 Omega(1)）。
动态表分析中势函数选择 χ = 2·num − size 是「让扩张时刻 χ=0」的精妙设计；试 χ = num − size 则无法得到常数摊还界。
装箱 / 页替换 / 哈希等场景常用摊还分析——记号虽不同但本质都是「最坏均值」。
与第 16 章贪心的耦合：贪心提供「结构」、摊还分析提供「最坏均值」——很多数据结构（如 Fibonacci 堆）依赖本章势能法证明复杂度。
引入「零势能初态」是关键技巧：让 Φ(D_0) = 0 并证明 Φ(D_i) ≥ 0，使摊还和直接成为上界。

第 17 章 摊还分析 (Amortized Analysis)

核心结论

一、核心概念

二、详细笔记

2.1 聚合分析

2.2 记账法

2.3 势能法

2.4 动态表扩张 (Table Expansion)

2.5 动态表扩张 + 收缩

三、关键图表

四、思维导图

五、重点与易错点

第 17 章摊还分析 (Amortized Analysis)