1. 概述
在本篇文章中，我们将介绍摊销分析（Amortized Analysis）这一技术，用于估算一组操作的总体运行时间成本。我们会通过两个常见的方法来讲解如何评估摊销成本：
- 聚合分析法（Aggregate Method）
- 记账法（Accounting Method）
这两种方法在分析数据结构操作序列时非常实用，尤其是当某些操作在个别情况下代价高昂，但在整体序列中表现良好时。
2. 摊销分析简介
设计高效算法时，通常会使用到数据结构。而数据结构的操作往往不是孤立进行的，而是以操作序列的形式出现。
如果我们想分析这类操作序列的时间复杂度，一个简单的方法是：对每个操作单独估算最坏情况下的运行时间，然后累加得到整个序列的上界。
在某些情况下这种方法是可行的。但很多时候，同一个操作在不同时间点的代价差异很大。例如，某些“昂贵”操作只在极少数情况下才会触发。
如果简单地累加所有操作的最坏情况代价，可能会严重高估整体运行时间。
摊销分析正是为了解决这个问题。它通过将“昂贵”操作的成本分摊到整个操作序列中，从而更准确地评估整体性能。
更正式地讲：摊销分析用于计算在最坏情况下，每个操作在整个操作序列中的平均代价。
为了更好地理解这个概念，我们以动态数组为例来说明。
3. 动态数组
我们考虑一个初始为空的数组 A，初始容量 N = 1，当前元素个数 n = 0。我们可以在数组末尾添加元素，但一旦数组满了，就需要扩容。
扩容操作通过复制整个数组到一个新的、容量为原来两倍的数组中完成。
3.1. append 操作
向动态数组中添加一个元素 x 的操作称为 append(x)，它包含两个步骤：
- 将 x 放入下一个可用位置
- 如果数组已满，则调用
copy()函数进行扩容
copy() 的作用是将原数组中的所有元素复制到一个容量为原来两倍的新数组中。
举个例子，假设当前数组如下：
执行 append(2) 后，数组变为：
4. 聚合分析法（Aggregate Method）
聚合分析法是一种“先总后分”的方法：
- 计算整个操作序列的最坏时间成本 T(n)
- 除以操作总数 n，得到每个操作的平均代价（即摊销代价）
公式如下：
$$ \text{Amortized operation cost} = \frac{T(n)}{n} $$
我们用这个方法来分析动态数组的 append 操作。
4.1. 动态数组的摊销分析
我们设每个简单的赋值操作耗时为 1 单位时间，用 Ci 表示第 i 次 append 的代价。
观察发现：
- 当 i 是 2 的幂（1, 2, 4, 8, ...）时，数组已满，需要扩容，代价为 i + 1
- 其他情况下，仅需赋值，代价为 1
因此：
$$ C_i = \begin{cases} i + 1, & \text{if } i \text{ is a power of 2} \ 1, & \text{otherwise} \end{cases} $$
总代价 T(n) 为所有 Ci 的和：
$$ T(n) = \sum_{i=1}^{n} C_i = \sum_{\substack{i \text{是} \ \text{2的幂}}} (i + 1) + \sum_{\substack{i \text{不是} \ \text{2的幂}}} 1 $$
进一步简化：
$$ T(n) = \sum_{\substack{i \text{是} \ \text{2的幂}}} i + n $$
由于 2 的幂最多出现 $\log_2 n$ 次，我们有：
$$ \sum_{j=0}^{\log_2 n} 2^j \leq 2n \Rightarrow T(n) \leq 3n $$
最后，摊销代价为：
$$ \frac{T(n)}{n} \leq \frac{3n}{n} = 3 = O(1) $$
4.2. 局限性
- 该方法适用于操作类型单一、结构清晰的序列
- 如果操作类型多样，它无法区分不同类型操作的摊销代价
- 不能为不同操作分配不同的“代价权重”
5. 记账法（Accounting Method）
记账法的核心思想是：为每个操作设定一个“收费”（amortized cost），并用这个收费来支付操作的实际代价。
- 如果操作实际代价 < 收费，余额存入“银行”
- 如果操作实际代价 > 收费，用银行余额补足
目标是：在廉价操作中积累足够的余额，用于支付后续昂贵操作
我们继续用动态数组来说明。
5.1. 动态数组的摊销分析
我们设定：
- 每个廉价
append实际代价为 $1 - 每个昂贵
append（含扩容）代价为 $(i + 1)
问题：我们应为每个 append 设置多少“收费”？
5.2. 确定“收费”金额
我们尝试不同的收费金额：
- $1：无法覆盖扩容代价 ❌
- $2：仍然不够 ❌
- $3：可以覆盖所有操作 ✅
我们可以用归纳法证明：只要每次 append 收 $3，银行余额始终非负
5.3. 证明
- 初始扩容代价为 $2，$3 足够支付 ✅
- 假设扩容后余额 ≥ 0，数组此时为半满
- 下一次扩容前，会有 N/2 - 1 次廉价操作，每次存 $2，共存 $(N - 2)
- 下次扩容代价为 $(*N + 1)，$3 收费 + $(*N - 2) 存款足够支付 ✅
因此，每个 append 的摊销代价为 $3 = O(1)
5.4. 多操作类型支持
- 聚合分析法：不能区分不同类型操作的摊销代价 ❌
- 记账法：可以为不同类型操作设置不同收费，从而得出各自的摊销代价 ✅
6. 总结
摊销分析是一种强大的工具，用于评估操作序列的整体代价，尤其适用于以下场景：
- 某些操作偶尔代价高昂
- 但整体表现良好
我们介绍了两种常见方法：
| 方法 | 优点 | 缺点 |
|---|---|---|
| 聚合分析法 | 简单直观 | 无法区分操作类型 |
| 记账法 | 可区分操作类型 | 需要合理设定“收费” |
通过动态数组的例子，我们看到：虽然扩容操作代价高昂，但通过摊销分析，我们可以证明其平均代价为 **O(1)**。
这在设计高效数据结构时具有重要意义。