摊还分析

概述

摊还分析（Amortized Analysis）是一种分析数据结构上操作序列总代价的技术，将总代价平均分摊到每个操作上，得到单个操作的摊还代价（amortized cost）。与平均情况分析不同，摊还分析不涉及概率假设，能够保证在最坏情况下每个操作的平均性能。

定义

摊还分析

给定一个数据结构 $D$ 及其上的 $n$ 个操作序列，设第 $i$ 个操作的实际代价为 $c_i$，则 $n$ 个操作的总代价为 ${\sum }_{i=1}^n{c}_i$。摊还分析的目标是证明： ${\sum }_{i=1}^n{c}_i\le {\sum }_{i=1}^n{\hat{c}}_i$ 其中 ${\hat{c}}_i$ 为第 $i$ 个操作的摊还代价。当所有 ${\hat{c}}_i$ 均为常数或某个简单函数时，我们就得到了每个操作的摊还上界。

核心性质

1. 不依赖概率：摊还分析不假设操作的输入分布，不涉及概率模型。它分析的是最坏情况下的操作序列，而非平均输入。
2. 序列整体保证：摊还分析保证的是操作序列的总代价上界，而非单个操作的上界。序列中某些操作的代价可能很高，但被其他低代价操作”补贴”了。
3. 三种经典方法：
   • 16.1 聚合分析（Aggregate Analysis）：直接求总代价上界，所有操作分配相同摊还代价
   • 16.2 记账方法（Accounting Method）：为不同操作分配不同摊还代价，差额作为信用存储
   • 16.3 势能方法（Potential Method）：将信用建模为整个数据结构的势能函数
4. 与平均情况分析的本质区别：平均情况分析需要假设输入的概率分布，且结论依赖于分布假设的正确性；摊还分析无需任何概率假设，结论对任意操作序列都成立。
5. 与竞争分析的关系：摊还分析是竞争分析（competitive analysis）在在线算法中的特例，常用于评估在线算法相对于最优离线算法的性能比。

章节扩展

方法	核心思想	适用特点
16.1 聚合分析	求总代价 $T(n)$，均摊为 $T(n)/n$	所有操作同类型或同代价
16.2 记账方法	超额收费存为信用，不足时消费信用	需要区分不同操作的代价
16.3 势能方法	定义势能函数 $\Phi$，用势能变化调节实际代价	需要全局视角，最灵活

典型应用场景

• Splay Tree：单次操作最坏 $O(n)$，但摊还 $O(\log n)$
• Union-Find（并查集）：使用路径压缩和按秩合并，摊还 $O(\alpha (n))$
• 斐波那契堆：Decrease-Key 摊还 $O(1)$，Delete 摊还 $O(\log n)$
• 动态数组（16.4 动态表）：插入摊还 $O(1)$，尽管偶尔需要 $O(n)$ 的扩容操作

参见

• 16.1 聚合分析 — 摊还分析的最直接方法
• 16.2 记账方法 — 基于信用存储的摊还分析
• 16.3 势能方法 — 基于势能函数的摊还分析
• 16.4 动态表 — 摊还分析的典型应用案例