【数据结构与算法体系】之摊还分析

一、为什么需要摊还分析

1.1 最坏情况分析的问题

传统的时间复杂度分析聚焦于单次操作的最坏情况。例如：

动态数组插入：最坏 $O(n)$（触发扩容时）
二叉堆插入：最坏 $O(\log n)$

但这可能过分悲观。以动态数组为例，$n$ 次连续插入的最坏总时间并非 $n \times O(n) = O(n^2)$，而是 $O(n)$。因为”触发扩容”是一个稀有事件——大多数插入只需 $O(1)$。

摊还分析（Amortized Analysis） 就是为了给出一系列操作的平均每次操作代价而设计的数学工具。

1.2 摊还分析 vs 平均情况分析

┌────────────────────┬──────────────────────┬─────────────────────┐
│     分析类型        │     考量对象          │     输入假设         │
├────────────────────┼──────────────────────┼─────────────────────┤
│ 最坏情况 (Worst)   │ 单次操作              │ 任意输入            │
│ 平均情况 (Average) │ 单次操作              │ 随机输入分布        │
│ 摊还 (Amortized)   │ 一系列操作的平均       │ 任意输入序列        │
└────────────────────┴──────────────────────┴─────────────────────┘

关键区别：摊还分析不假设输入满足任何概率分布。它给出的是任何操作序列上的平均保证。

二、聚合分析法（Aggregate Method）

2.1 方法描述

聚合分析是最直接的方法：对一个长度为 $n$ 的操作序列，计算总代价 $T(n)$，则每个操作的摊还代价为 $T(n)/n$。

2.2 案例一：动态数组（Dynamic Table）

命题：对最初为空的动态数组执行 $n$ 次 push 操作，总时间为 $O(n)$，每个操作的摊还代价为 $O(1)$。

分析：设扩容策略为”容量满时翻倍”。令 $c_i$ 为第 $i$ 次 push 的代价。

若不触发扩容：$c_i = 1$（一次赋值）
若触发扩容：$c_i = 1 + (i-1)$（一次赋值 + $i-1$ 次复制）

扩容发生在 $i = 1, 2, 4, 8, \ldots, 2^{\lfloor \log_2 n \rfloor + 1}$ 时。设 $2^{k-1} < n \leq 2^k$。

总代价：

$$T(n) = \sum_{i=1}^{n} c_i = n + \sum_{j=0}^{\lfloor \log_2 n \rfloor} 2^j$$

等比数列求和：$\sum_{j=0}^{k-1} 2^j = 2^k - 1 \leq 2 \cdot 2^{k-1} < 2n$

因此 $T(n) = n + (2^k - 1) < n + 2n = 3n = O(n)$。

摊还代价：$T(n) / n = O(1)$。

// 动态数组的摊还分析——聚合视角
// 复制成本：1 + 2 + 4 + 8 + ... + 2^k < 2n
// 赋值成本：n
// 总：< 3n = O(n)
class DynamicArray<E> {
    Object[] data;
    int size;
    
    @SuppressWarnings("unchecked")
    public E push(E item) {
        // 摊还O(1) —— 聚合分析证明
        if (size == data.length) resize(data.length * 2);
        data[size++] = item;
        return item;
    }
}

2.3 案例二：二进制计数器（Binary Counter）

命题：从一个初始为 0 的 $k$ 位二进制计数器开始，执行 $n$ 次递增（INCREMENT）操作，总位翻转次数为 $O(n)$。

分析：考虑 $n$ 次递增过程中，每一位翻转的次数：

最低位（bit 0）：每次递增都翻转 → $n$ 次
bit 1：每 2 次递增翻转 1 次 → $\lfloor n/2 \rfloor$ 次
bit 2：每 4 次递增翻转 1 次 → $\lfloor n/4 \rfloor$ 次
一般地，bit $j$：翻转 $\lfloor n / 2^j \rfloor$ 次

总翻转次数：

$$T(n) = \sum_{j=0}^{k-1} \left\lfloor \frac{n}{2^j} \right\rfloor \leq n \sum_{j=0}^{\infty} \frac{1}{2^j} = n \cdot 2 = 2n = O(n)$$

几何级数求和给了上限 $2n$。因此每次 INCREMENT 的摊还代价为 $O(1)$，尽管某一次递增可能翻转多达 $k = \Theta(\log n)$ 位。

// 二进制计数器模拟，展示聚合分析
class BinaryCounter {
    public static int totalFlips(int n, int bits) {
        int total = 0;
        for (int j = 0; j < bits; j++) {
            total += n / (1 << j); // bit j 翻转 n/2^j 次
        }
        return total;
    }
    // 例如：n=16, bits=8, totalFlips = 16 + 8 + 4 + 2 + 1 + 0 + 0 + 0 = 31 < 2*16
}

2.4 聚合分析的小结

优点：直接明了，通过对总代价求和得到了界。
缺点：当操作类型不统一时（如既有 push 又有 pop），聚合分析无法区分不同操作的摊还代价。

三、记账法（Accounting Method）

3.1 方法描述

记账法为每种操作分配一个**摊还代价 $\hat{c}_i$**（可能与实际代价 $c_i$ 不同）。多余的代价作为”信用（credit）”存入数据结构，不足时用之前存储的信用弥补。

关键约束：对于任意长度为 $n$ 的操作序列，总摊还代价必须不小于总实际代价：

$$\sum_{i=1}^{n} \hat{c}i \geq \sum{i=1}^{n} c_i$$

即数据结构中的信用余额始终非负。

3.2 案例一：栈 with MultiPop

考虑支持三种操作的栈：

PUSH(x)：实际代价 1
POP()：实际代价 1
MULTIPOP(k)：弹出 $\min(k, size)$ 个元素，实际代价 $\min(k, size)$

记账方案：

PUSH(x)：摊还代价 $\hat{c} = 2$（1 支付 push + 1 存入信用）
POP()：摊还代价 $\hat{c} = 0$（用 1 信用支付 pop）
MULTIPOP(k)：摊还代价 $\hat{c} = 0$（所有弹出的元素都已预存信用）

信用不变式：栈中每个元素携带 1 单位信用（恰好足够支付其被 pop 的代价）。

验证：

PUSH：元素入栈带 1 信用 → 余额增加
POP：消费栈顶元素的信用 → 余额减少，但始终 ≥ 0
MULTIPOP：消费被弹出元素的信用 → 同理

任意 $n$ 次操作的总摊还代价 ≤ $\sum \hat{c}_i \leq 2n$（最多 $n$ 次 PUSH）。因此所有操作都是 $O(1)$ 摊还。

// 记账法在代码中表现为"概念上的信用追踪"
class AccountingStack<E> {
    Deque<E> stack = new ArrayDeque<>();
    // 信用模型：每次push额外支付1单位，存入每个元素
    // pop时消费该信用
    // 不需要实际代码改变，只是分析工具
    
    void push(E item) {
        stack.push(item);
        // 实际代价: 1, 摊还代价: 2, 信用+1
    }
    
    E pop() {
        // 实际代价: 1, 摊还代价: 0, 信用-1
        return stack.pop();
    }
}

3.3 案例二：动态数组（记账法视角）

记账方案：

每次 push（不触发扩容）：摊还代价 $\hat{c} = 3$
- 1 支付自身的赋值
- 1 作为该元素的信用（用于日后自己被复制时支付）
- 1 作为给”配对的老元素”的信用（帮助老元素支付被复制的代价）
扩容时复制：摊还代价 $\hat{c} = 0$（所有被复制的元素已预先存有信用）

关键洞察：当数组从容量 $m$ 扩容到 $2m$ 时，新数组前半部分的 $m$ 个元素已经在过去被”多存”了信用，恰好支付当前复制的代价。

验证摊还界：每次 push 摊还 ≤ 3，$n$ 次操作总摊还 ≤ $3n$，因此摊还 $O(1)$。

四、势能法（Potential Method）——最强大的工具

4.1 方法描述

势能法定义了一个**势能函数 $\Phi$**，将数据结构的状态 $D$ 映射为一个实数 $\Phi(D) \geq 0$。初始状态 $D_0$ 满足 $\Phi(D_0) = 0$。

第 $i$ 次操作的摊还代价定义为：

$$\hat{c}i = c_i + \Phi(D_i) - \Phi(D{i-1})$$

其中 $c_i$ 是实际代价，$\Delta\Phi = \Phi(D_i) - \Phi(D_{i-1})$ 是势能变化。

总摊还代价：

$$\sum_{i=1}^{n} \hat{c}i = \sum{i=1}^{n} c_i + \Phi(D_n) - \Phi(D_0) \geq \sum_{i=1}^{n} c_i$$

（因为 $\Phi(D_n) \geq 0 = \Phi(D_0)$）——这正是我们需要的不等式。

4.2 案例一：栈 with MultiPop

定义势能函数 $\Phi(D) = \text{当前栈中的元素个数}$。

PUSH：$c_i = 1$，$\Delta\Phi = +1$，$\hat{c}_i = 1 + 1 = 2$
POP：$c_i = 1$，$\Delta\Phi = -1$，$\hat{c}_i = 1 - 1 = 0$
MULTIPOP(k)：$c_i = k$，$\Delta\Phi = -k$，$\hat{c}_i = k - k = 0$

所有操作摊还 $O(1)$。

4.3 案例二：动态数组（势能法）

定义势能函数：$\Phi(D) = 2 \cdot size - capacity$（当 $capacity > 0$）。

直观解释：势能衡量的是数组的”装满程度”。刚好满时 $\Phi = 2 \cdot cap - cap = cap$，势能高；half-full 时 $\Phi = 2 \cdot (cap/2) - cap = 0$，势能为零。

push 不扩容（$size < capacity$）：
$c_i = 1$
$\Delta\Phi = [2(size+1) - cap] - [2 \cdot size - cap] = 2$
$\hat{c}_i = 1 + 2 = 3$
push 扩容（$size = capacity = m$）：
$c_i = 1 + m$（1 赋值 + m 复制）
扩容前：$\Phi_{before} = 2m - m = m$
扩容后：$capacity = 2m$，$size = m+1$（刚插入后），$\Phi_{after} = 2(m+1) - 2m = 2$
$\Delta\Phi = 2 - m = m - 2$（负的，因为势能被释放）
$\hat{c}_i = (1 + m) + (2 - m) = 3$

统一结论：每次 push 的摊还代价为 3，总 $n$ 次 push 总代价 ≤ $3n = O(n)$。

4.4 案例三：二进制计数器（势能法）

定义势能函数 $\Phi(D) = \text{当前计数器中 1 的个数}$。

设第 $i$ 次 INCREMENT 将 $t_i$ 个 1 翻转为 0，最后将 1 个 0 翻转为 1。实际代价 $c_i = t_i + 1$。

势能变化：

翻转 $t_i$ 个 1→0：势能减少 $t_i$
翻转 1 个 0→1：势能增加 $1$
$\Delta\Phi = 1 - t_i$

摊还代价：
$$\hat{c}_i = (t_i + 1) + (1 - t_i) = 2$$

每次 INCREMENT 摊还 $O(1)$！

4.5 势能函数的选择艺术

势能法的核心挑战在于选择恰当的势能函数。好的势能函数满足：

$\Phi(D_0) = 0$ 且 $\Phi(D) \geq 0$ 对任意 $D$
摊还代价 $\hat{c}_i$ 易于计算
摊还代价的上界有意义（通常是 $O(1)$ 或 $O(\log n)$）

通用启发式：势能函数通常衡量数据结构的”混乱度”或”工作量欠债”。当数据结构处于一个操作昂贵的状态时，势能应该高（相当于提前储蓄了能量）；执行完昂贵操作后势能降低。如果势能始终为正，说明总摊还代价 ≥ 总实际代价。

五、三种方法的对比与实践指南

┌─────────────┬──────────────────┬──────────────────┬──────────────────┐
│   方法       │     核心思想      │     优势          │     劣势          │
├─────────────┼──────────────────┼──────────────────┼──────────────────┤
│ 聚合分析     │ 直接求和/T(n)/n  │ 思路直观,易验证    │ 无法区分操作类型  │
│ 记账法       │ 信用预存与消费    │ 区分多种操作类型  │ 信用设计需要巧思  │
│ 势能法       │ 势能函数的Δ       │ 最通用,最强大     │ 势能函数难构造    │
└─────────────┴──────────────────┴──────────────────┴──────────────────┘

实践建议：对于简单的”一种操作”场景（动态数组、二进制计数器），聚合分析最直接。对于有多种操作的场景（栈的 MultiPop），势能法或记账法更自然。面试中，动态数组和二进制计数器是最高频的摊还分析考点——两者用聚合分析就足够清晰。

六、摊还分析在高级数据结构中的应用概览

6.1 斐波那契堆（Fibonacci Heap）

斐波那契堆的 decrease-key 操作摊还 $O(1)$ 而实际最坏情况可能为 $O(n)$（级联切断）。势能函数：$\Phi(H) = t(H) + 2m(H)$，其中 $t(H)$ 是根链表中的树的数量，$m(H)$ 是已标记节点的数量。

这使得 Dijkstra 算法和 Prim 算法在理论上可以达到更优的复杂度（$O(m + n \log n)$ vs $O(m \log n)$）。

6.2 并查集（Union-Find）

带路径压缩和按秩合并的并查集，union 和 find 操作的摊还代价为 $O(\alpha(n))$，其中 $\alpha(n)$ 是反 Ackermann 函数（对于任何可实践的 $n$，$\alpha(n) \leq 5$）。

6.3 Splay 树（Splay Tree）

Splay 树的每次操作（查找、插入、删除）摊还 $O(\log n)$，但单次操作最坏可能需要 $\Theta(n)$。摊还分析使用势能函数 $\Phi(T) = \sum_{x \in T} \log(\text{size of subtree rooted at } x)$，利用旋转操作中的势能释放来支付操作的总成本。

6.4 总结表

┌──────────────┬──────────────┬──────────────────────┐
│   数据结构    │  关键操作     │   摊还代价            │
├──────────────┼──────────────┼──────────────────────┤
│ 动态数组     │ push         │ O(1)                 │
│ 二进制计数器  │ INCREMENT    │ O(1) (每操作)        │
│ 栈+MultiPop  │ 全部操作      │ O(1) (每操作)        │
│ 斐波那契堆   │ decrease-key │ O(1)                 │
│ 并查集(优化) │ find/union   │ O(α(n)) ≈ O(1)       │
│ Splay树      │ 查找         │ O(log n)             │
└──────────────┴──────────────┴──────────────────────┘

七、面试常见追问

问题一：动态数组扩容为什么用 1.5x 而不是 2x？从摊还角度怎么分析？

回答：从摊还角度，扩容因子 $\alpha$ 决定摊还成本：

摊还成本 $\approx \frac{\alpha}{\alpha - 1}$（见上文的等比级数推导）

$\alpha = 2$：摊还 $\approx \frac{2}{1} = 2$ 次基本操作
$\alpha = 1.5$：摊还 $\approx \frac{1.5}{0.5} = 3$ 次基本操作
$\alpha = 1.1$：摊还 $\approx \frac{1.1}{0.1} = 11$ 次基本操作

单纯从摊还时间角度看，$\alpha$ 越大越省时间。但 $\alpha$ 越大也意味着越大的空间浪费。1.5x 是在时间和空间之间的工程平衡。另一个微妙的原因是内存分配器：1.5x 扩容后，之前释放的内存块总大小有希望满足新的分配需求（reuse），而 2x 扩容永远不可能重用（前一块 Released 的总大小 < 下一块的需求）。

问题二：势能函数必须满足 $\Phi(D_0) = 0$ 且始终 $\geq 0$。如果在某步 $\Phi(D_i) < 0$ 会发生什么？

回答：势能必须始终非负，因为我们需要 $\sum \hat{c}_i = \sum c_i + \Phi(D_n) - \Phi(D_0) \geq \sum c_i$ 恒成立。如果某一步 $\Phi(D_i) < 0$，虽然从 $D_i$ 到 $D_n$ 的总摊还仍可能正确，但势能法推理的中途步骤不再有保证——我们无法确保在每个操作处，积聚的”势能储备”足够支付昂贵的操作。

如果势能在某一步为负，意味着我们的势能函数设计有问题——它在该步骤”预支”了尚未储蓄的能量。一个合法的势能函数必须从始至终 $\geq 0$。

问题三：聚合分析、记账法和势能法之间有什么关系？

回答：三者是等价的——任何能用摊还分析证明的界，用三种方法之一都可做到。但它们在应用上不同：

聚合法是势能法在 $\Phi = 0$ 时的退化特例（不做预存/释放，只是事后统计）
记账法可视为势能法的”离散化”版本：将势能分配到每个元素上（每个元素携带固定信用），信用总和 = $\Phi(D)$
势能法最通用，记账法中的”信用”可以视为势能的一种表现形式

在实践中，选择一个构造最自然的方法即可。

问题四：一个数据结构的不同操作可能有不同的摊还代价，如何用势能法同时分析多个操作？

回答：使用同一个势能函数 $\Phi(D)$，分别计算每种操作的 $\hat{c} = c + \Delta\Phi$。例如在斐波那契堆中：

insert：$c = O(1)$，$\Delta\Phi = +1$（多一棵根树），$\hat{c} = O(1)$
extract-min：$c = O(\log n)$（合并 + 堆化），$\Delta\Phi \leq O(\log n) \text{（减少根树数量）}$，$\hat{c} = O(\log n)$
decrease-key：$c$ 可能 $O(n)$（级联切断），但 $\Delta\Phi$ 大幅为负（被切断的标记节点失去标记），$\hat{c} = O(1)$

同一个 $\Phi$ 统一处理所有操作——这就是势能法的威力。

问题五：实际工程中什么时候需要自己进行摊还分析？

回答：

设计自定义容器：当你需要实现类似 Dynamic Array 的结构，选择合适的扩容策略（1.5x? 2x? 固定增量？）
系统设计中的批处理/缓冲区：写入缓冲区的刷新策略——可以类比动态数组的扩容，摊还分析给出每次写入的均摊成本
理解 Java Collections 的性能保证：ArrayList.add() 的”constant amortized time”保证背后的数学依据
代码审查：识别那些”最坏情况分析让人却步，但实际序列中很少触发”的代码

八、势能法进阶：以 $k$-bit 计数器为例的严密推导

让我们更系统地展示势能法的完整步骤。考虑一个 $k$ 位二进制计数器，支持 INCREMENT 操作。

步骤 1：定义势能函数
$$\Phi(D) = \text{bit count of 1’s in } D$$

步骤 2：分析一次操作

设第 $i$ 次 INCREMENT 从低位开始连续翻转了 $t_i$ 个 1 变成 0，最后将遇到的第一个 0 翻转为 1。则：

实际代价：$c_i = t_i + 1$（每次翻转成本为 1）
翻转前 1 的个数：设为 $b_{i-1}$
翻转后 1 的个数：$b_i = b_{i-1} - t_i + 1$
势能变化：$\Delta\Phi_i = b_i - b_{i-1} = 1 - t_i$

步骤 3：计算摊还代价
$$\hat{c}_i = c_i + \Delta\Phi_i = (t_i + 1) + (1 - t_i) = 2$$

步骤 4：得出上界
$$\sum_{i=1}^{n} c_i = \sum_{i=1}^{n} \hat{c}i - (\Phi_n - \Phi_0) \leq \sum{i=1}^{n} 2 = 2n$$

因为 $\Phi_0 = 0$ 且 $\Phi_n \geq 0$，所以总实际代价 $\leq 2n = O(n)$。

这个推导的有趣之处在于：摊还代价恒为 2，与计数器的大小 $k$ 无关！即使 $k = 1000$，平均每次 INCREMENT 也只翻转 2 个 bit。这就是为什么二进制计数器在硬件中如此高效。

九、总结

摊还分析是算法设计中理解”平均行为”的数学语言：

聚合分析：总代价/操作次数，简单直接
记账法：为操作分配信用，直观模拟”预存”与”消费”
势能法：定义势能函数，最通用也最需要巧思

三个核心案例：

动态数组 push：摊还 $O(1)$（$\Phi = 2 \cdot size - capacity$）
二进制计数器 INCREMENT：摊还 $O(1)$（$\Phi$ = 1 的个数）
栈 MultiPop：摊还 $O(1)$（$\Phi$ = 元素个数）

摊还分析是后续高级数据结构（斐波那契堆、Splay 树、并查集）复杂度分析的共同语言。下一篇【数据结构与算法体系】斐波那契堆 将展示摊还分析如何解释 decrease-key 的 $O(1)$ 奇迹。