摊还分析

分析算法时通常关注单次操作的最坏情况复杂度

但在许多场景中，数据结构经历一系列操作，虽然某些单次操作代价很高，但高代价操作不会频繁发生

核心场景：维护一个数据结构，执行 $n$ 次操作 $o_1, o_2, \ldots, o_n$

单次操作的代价可能很大（如 $\Theta(n)$）
但总代价可能远小于 $n \times \max c(o_i)$
摊还分析：在这种场景下精确分析总代价

经典例子：Heapify 单次 $O(\log n)$，但 Build-Heap（$n$ 次 Heapify）总代价为 $O(n)$ 而非 $O(n \log n)$

摊还分析不是平均情况分析
不对输入序列做任何概率假设
仍然是最坏情况原则——给出任何操作序列的总代价上界

摊还分析技术

技术	核心思想	灵活性
聚合法	直接计算总代价，取平均	最低
记账法	为操作分配”信用”，维护银行账户	中等
势能法	将预存的工作建模为势能	最高

以二进制计数器为例阐述三种方法，然后转向动态表问题

摊还代价定义

\[ \hat{c} = \max_{\text{序列}} \frac{\sum_{i=1}^n c(o_i)}{n} \]

一次操作在最坏操作序列上的平均代价，对所有 $n$ 和所有操作序列取最大

	最坏情况分析	平均情况分析	摊还分析
关注点	单次操作最坏代价	随机输入的期望代价	操作序列的总代价
假设	无	需要输入分布	无（最坏情况序列）
结论	每次操作上界	期望每次操作代价	摊还上界

聚合法：先计算总代价，再除以 $n$

后续方法：先设定摊还代价，再证明总代价上界

二进制计数器

数据结构：$k$ 位二进制数组，用于计数从 0 到 $2^k - 1$

操作：递增 (Increment)

代价：翻转的位数

示例

计数器状态    翻转的位    代价
00000
00001        A[0]: 0→1    1
00010        A[0]: 1→0, A[1]: 0→1    2
00011        A[0]: 0→1    1
00100        A[0]: 1→0, A[1]: 1→0, A[2]: 0→1    3
00101        A[0]: 0→1    1
00110        A[0]: 1→0, A[1]: 0→1    2
00111        A[0]: 0→1    1
01000        A[0]: 1→0, A[1]: 1→0, A[2]: 1→0, A[3]: 0→1    4

最坏情况分析：单次递增最多翻转 $k$ 位，$n$ 次递增的朴素上界 $O(nk)$，但这个上界太松了

聚合法

方法描述

直接计算 $n$ 次操作的总代价，然后取平均。所有操作有相同的摊还代价

按列计数（换个角度）：计算每一位被翻转了多少次

第 0 位（最低位）：每次递增都翻转 → $n$ 次
第 1 位：每 2 次递增翻转 → $\lfloor n/2 \rfloor$ 次
第 2 位：每 4 次递增翻转 → $\lfloor n/4 \rfloor$ 次
第 $i$ 位：每 $2^i$ 次递增翻转 → $\lfloor n/2^i \rfloor$ 次

递增序列:
0  0  0  0  0
0  0  0  0  1    代价 = 1
0  0  0  1  0    代价 = 2
0  0  0  1  1    代价 = 1
0  0  1  0  0    代价 = 3
0  0  1  0  1    代价 = 1
...
翻转次数:  1  2  4  8  16  ← 第 i 列的翻转次数 = ⌊n/2^i⌋

\[ \text{总代价} = \sum_{i=0}^{k-1} \left\lfloor \frac{n}{2^i} \right\rfloor \leq \sum_{i=0}^{\infty} \frac{n}{2^i} = n \cdot \frac{1}{1 - \frac{1}{2}} = 2n \]

总代价 $= O(n)$
摊还代价 $= O(1)$

扩展：非均匀代价的二进制计数器

若翻转第 $i$ 位的代价为 $2^i$：

\[ \text{总代价} = \sum_{i=0}^{k-1} \left\lfloor \frac{n}{2^i} \right\rfloor \cdot 2^i \leq \sum_{i=0}^{k-1} n = nk \]

在这种情况下聚合法没有给出更好的结果

记账法

方法描述

数据结构关联一个”银行账户”

每次操作被分配一个固定金额（摊还代价）
实际代价小于分配金额：多余的钱存入银行
实际代价大于分配金额：从银行取钱支付
不同操作可以有不同的摊还代价

要求：银行余额永远不能为负 \[ \sum_{i=1}^{n} \hat{c}(o_i) \geq \sum_{i=1}^{n} c(o_i) \quad \text{对所有 } n \text{ 和所有操作序列} \]

应用于二进制计数器

摊还代价： - 翻转 $0 \to 1$：支付 $2 - 翻转 $1 \to 0$：支付 $0

分析：将 $0$ 翻转为 $1$ 时，$1 执行翻转，$1 存入银行（预留给将来该位 $1 \to 0$）

将 $1$ 翻转为 $0$ 时，使用之前预存的 $1

不变量：计数器中每个为 1 的位在银行中都有 $1 预留，余额永远非负

每次递增只执行一次 $0 \to 1$ 翻转，摊还代价 $2，$n$ 次递增总代价 $\leq 2n = O(n)$

势能法

方法描述

将”预存的工作”看作整个数据结构的势能

定义势能函数 $\Phi: \{D_i\} \to \mathbb{R}$

\[ \hat{c}_i = c_i + \Phi(D_i) - \Phi(D_{i-1}) \]

摊还代价 = 实际代价 + 势能变化

$\Delta\Phi > 0$：操作增加势能，必须”付费”，摊还代价高于实际
$\Delta\Phi < 0$：势能释放帮助支付，摊还代价低于实际

基本规则

势能函数必须满足： 1. $\Phi(D_0) = 0$（初始势能为零） 2. $\Phi(D_i) \geq 0$ 对所有 $i$ 成立

正确性证明

\[ \sum_{i=1}^{n} \hat{c}_i = \sum_{i=1}^{n} (c_i + \Phi(D_i) - \Phi(D_{i-1})) \]

右边：$= \sum_{i=1}^{n} c_i + \Phi(D_n) - \Phi(D_0)$

由 $\Phi(D_n) \geq 0$ 且 $\Phi(D_0) = 0$：

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

总摊还代价是总实际代价的上界

应用于二进制计数器

势能函数：$\Phi(\text{Counter}) = \text{计数器中 1 的个数}$

递增操作将 $t$ 个 1 翻转为 0，1 个 0 翻转为 1：$\Delta\Phi = 1 - t$

\[ \hat{c}_i = c_i + \Delta\Phi = (1 + t) + (1 - t) = 2 \]

高代价操作（$t$ 大）大幅降低势能，低代价操作增加势能，完美补偿

动态表

问题描述

有一个表（动态数组），需要支持 INSERT

表满时分配更大的表并复制所有元素

策略：表满时翻倍

\[c_i = \begin{cases} i & \text{如果 } i - 1 \text{ 恰好是 2 的幂（需翻倍，复制 } i-1 \text{ 旧元素加插入）} \\ 1 & \text{否则} \end{cases}\]

单次 INSERT 最坏 $\Theta(n)$，朴素上界 $\Theta(n^2)$，但实际总代价为 $\Theta(n)$

聚合分析

i     Size    Cost
1      1       1
2      1       1+1 = 2    (翻倍)
3      2       1+2 = 3    (翻倍)
4      4       1
5      4       1+4 = 5    (翻倍)
6      8       1
7      8       1
8      8       1
9      8       1+8 = 9    (翻倍)
10     16      1

\[ \sum_{i=1}^{n} c_i = n + \sum_{j=0}^{\lfloor \lg(n-1) \rfloor} 2^j \leq n + 2n = 3n \]

翻倍复制的代价是等比数列之和 $1 + 2 + 4 + \ldots \leq 2n$

总代价 $O(n)$，摊还代价 $O(1)$

记账分析

每次 INSERT 收 $3： - $1：支付本次插入 - $1：为将来自己被复制预存 - $1：为将来复制一个”旧元素”预存

1
2
3

表状态: [旧元素: $0] [旧元素: $0] ... | [新半区: 每个元素 $2]
                                       ↑
                                  半满之后插入的元素各存了 $2

从半满填到全满过程中，每次 INSERT 存入 $2。到表满时，后半段恰好有 $\text{size}/2$ 个元素各存 $2，共 $\text{size}$ 元，正好支付翻倍时复制的代价

势能分析（仅 INSERT）

$\Phi(D_i) = 2 \cdot \text{num}_i - \text{size}_i$

约定 $\Phi(D_0) = 0$，当 $\text{num}_i \geq \text{size}_i / 2$ 时 $\Phi(D_i) \geq 0$

情况 1：第 $i$ 次 INSERT 不触发扩展

$\text{size}_i = \text{size}_{i-1}$，$\text{num}_i = \text{num}_{i-1} + 1$

\[\hat{c}_i = 1 + (2\text{num}_i - \text{size}_i) - (2\text{num}_{i-1} - \text{size}_{i-1}) = 1 + 2 - 0 = 3\]

情况 2：触发扩展

$\text{size}_i = 2\text{size}_{i-1}$，$\text{num}_{i-1} = \text{size}_{i-1}$，$\text{num}_i = \text{num}_{i-1} + 1$

$c_i = \text{num}_{i-1} + 1$

\[\hat{c}_i = (\text{num}_{i-1} + 1) + (2(\text{num}_{i-1} + 1) - 2\text{size}_{i-1}) - (2\text{num}_{i-1} - \text{size}_{i-1})\]

\[= (\text{num}_{i-1} + 1) + 2 - \text{size}_{i-1} = (\text{num}_{i-1} + 1) + 2 - \text{num}_{i-1} = 3\]

两种情况摊还代价都是 3，$n$ 次 INSERT 总代价 $\leq 3n = O(n)$

扩展与收缩

实际中还需要 DELETE，删除可能导致表过于稀疏，需要收缩

策略：溢出 → 翻倍，元素数 $< \text{size}/4$ → 减半

为什么不在 $< \text{size}/2$ 时减半？

考虑表恰好满时的交替插入-删除序列，每次都触发翻倍/减半，每次 $\Theta(n)$，这就是抖动

选择 $1/4$ 阈值在半满和全满之间有足够”缓冲区”

势能函数

\[\Phi(D_i) = \begin{cases} 2 \cdot \text{num}_i - \text{size}_i & \text{如果 } \text{num}_i \geq \text{size}_i / 2 \\ \text{size}_i / 2 - \text{num}_i & \text{如果 } \text{num}_i < \text{size}_i / 2 \end{cases}\]

设计思想： - 超过半满时：越满势能越高，为翻倍预存 - 不到半满时：越空势能越高，为减半预存 - 恰好半满时：$\Phi = 0$，平衡点

$\Phi(D_i) \geq 0$ 对所有 $i$ 成立

点击查看情况分析

INSERT，$\alpha_{i-1} \geq 1/2$，不触发扩展：

\[\hat{c}_i = 1 + (2\text{num}_i - \text{size}_i) - (2\text{num}_{i-1} - \text{size}_{i-1}) = 1 + 2 = 3\]

INSERT，$\alpha_{i-1} < 1/2$ 且 $\alpha_i < 1/2$：

\[\hat{c}_i = 1 + (\text{size}_i/2 - \text{num}_i) - (\text{size}_{i-1}/2 - \text{num}_{i-1}) = 1 - 1 = 0\]

DELETE，不触发收缩，$\alpha_{i-1} < 1/2$：

\[\hat{c}_i = 1 + (\text{size}_i/2 - \text{num}_i) - (\text{size}_{i-1}/2 - \text{num}_{i-1}) = 1 + 1 = 2\]

DELETE，触发收缩（$\text{num}_{i-1} = \text{size}_{i-1}/4$）：

$\text{size}_i = \text{size}_{i-1}/2$，$\text{num}_i = \text{num}_{i-1} - 1 = \text{size}_{i-1}/4 - 1$

$c_i = 1 + \text{num}_i = \text{size}_{i-1}/4$

经计算，摊还代价同样为常数

INSERT 和 DELETE 的摊还代价都是 $O(1)$，$n$ 次混合操作总代价 $O(n)$

三种方法的比较

特征	聚合法	记账法	势能法
分析对象	总代价	每次操作的”信用”	数据结构的”势能”
所有操作代价相同？	是（平均）	否（可不同）	否（可不同）
需要维护什么？	总代价的计算	余额 $\geq 0$	势能 $\geq 0$
灵活性	低	中	高
适用场景	操作单一	多种操作	最复杂场景

记账法和势能法本质等价：银行余额 $= \sum \hat{c}_i - \sum c_i = \Phi(D_n)$

势能法更形式化和系统化，记账法直觉更清晰

选择指南

聚合法：只有一种操作类型且总代价容易直接计算
记账法：多种操作类型，每种操作的”预存”有自然直觉
势能法：需要最大灵活性，特别是有 INSERT + DELETE 混合操作、代价依赖全局状态

势能函数设计模式

数据结构	什么使其”坏”	势能函数
二进制计数器	多个 1（清零代价高）	1 的个数
动态数组（仅 INSERT）	接近满（翻倍代价高）	$2\text{num} - \text{size}$
栈	元素多（MULTIPOP 代价高）	元素数量
斐波那契堆	根表长（CONSOLIDATE 代价高）	根节点数 $+ 2 \times$ 标记节点数
Splay 树	不平衡	$\sum \log(\text{子树大小})$

设计原则： 1. 势能衡量数据结构离”灾难性事件”有多近 2. 便宜操作增加势能 3. 昂贵操作大幅降低势能 4. 势能始终非负

Splay 树——势能法的高级应用

Splay 树是 Sleator 和 Tarjan (1985) 发明的自调整二叉搜索树，每次访问一个节点后通过旋转将其移到根

势能函数：

\[ \Phi(T) = \sum_{v \in T} \log_2 |T_v| \]

$|T_v|$ 是以 $v$ 为根的子树大小

完全平衡树：$\Phi = O(n)$
退化链：$\Phi = O(n \log n)$

Access Lemma：splay 操作的摊还代价 $\leq 3(\log n - \log |T_x|) + 1 = O(\log n)$

每次操作在将节点移到根的同时降低势能，势能的降低补偿了旋转代价

摊还分析的重要性与应用

避免朴素分析的过度悲观，有确定性保证，不依赖概率假设

常见应用

数据结构/算法	最坏单次代价	摊还代价
二进制计数器	$O(k)$	$O(1)$
动态数组（翻倍）	$O(n)$	$O(1)$
斐波那契堆 DECREASE-KEY	$O(n)$	$O(1)$
Splay 树	$O(n)$	$O(\log n)$
Union-Find（路径压缩+按秩）	$O(\log n)$	$O(\alpha(n))$
Link-Cut 树	$O(n)$	$O(\log n)$

摊还分析 vs 期望分析

摊还分析：确定性保证，对任何输入序列成立
期望分析：概率保证，对随机选择成立

可以组合使用，例如 Splay 树的随机分析

动态表的增长因子权衡

增长因子	摊还插入代价	最大空间浪费
2（翻倍）	$O(1)$	50%
1.5	$O(1)$	33%
1.125（Python）	$O(1)$	12.5%
1（不增长）	$O(n)$	0%

所有大于 1 的常数增长因子都保证 $O(1)$ 摊还代价，差别仅在常数因子

Python 列表选择约 12.5% 的增长率，牺牲少量摊还常数换取更好的空间利用率

从摊还到竞争分析

势能法是在线算法竞争分析的主要工具：

摊还分析：比较”实际总代价”与”摊还代价之和”
竞争分析：比较”在线算法总代价”与”最优离线算法总代价”

定义势能为在线算法状态与最优离线状态的”差距”，证明在线算法的摊还代价不超过最优算法的 $c$ 倍

例：LRU 缓存替换是 $k$-竞争的（$k$ 为缓存大小）

数据结构/算法	最坏单次代价	摊还代价
二进制计数器	\(O(k)\)	\(O(1)\)
动态数组（翻倍）	\(O(n)\)	\(O(1)\)
斐波那契堆 DECREASE-KEY	\(O(n)\)	\(O(1)\)
Splay 树	\(O(n)\)	\(O(\log n)\)
Union-Find（路径压缩+按秩）	\(O(\log n)\)	\(O(\alpha(n))\)
Link-Cut 树	\(O(n)\)	\(O(\log n)\)

(´-ω-｀)

摊还分析技术

摊还代价定义

二进制计数器

示例

聚合法

方法描述

扩展：非均匀代价的二进制计数器

记账法

方法描述

应用于二进制计数器

势能法

方法描述

基本规则

正确性证明

应用于二进制计数器

动态表

问题描述

聚合分析

记账分析

势能分析（仅 INSERT）

扩展与收缩

势能函数

更多示例

栈操作

用两个栈实现队列

三种方法的比较

选择指南

势能函数设计模式

Splay 树——势能法的高级应用

摊还分析的重要性与应用

常见应用

摊还分析 vs 期望分析

动态表的增长因子权衡

从摊还到竞争分析

摊还分析

(´-ω-｀)

摊还分析

摊还分析技术

摊还代价定义

二进制计数器

示例

聚合法

方法描述

扩展：非均匀代价的二进制计数器

记账法

方法描述

应用于二进制计数器

势能法

方法描述

基本规则

正确性证明

应用于二进制计数器

动态表

问题描述

聚合分析

记账分析

势能分析（仅 INSERT）

扩展与收缩

势能函数

更多示例

栈操作

用两个栈实现队列

三种方法的比较

选择指南

势能函数设计模式

Splay 树——势能法的高级应用

摊还分析的重要性与应用

常见应用

摊还分析 vs 期望分析

动态表的增长因子权衡

从摊还到竞争分析

摊还分析

同分类文章