Algorithm---Amortized Analysis: Accounting Method

本文讲解简单讲解一下 Amortized Analysis 里的 Accounting Method。

1. 基本概念

均摊分析关注的是**一系列操作（Sequence of operations）**的总成本，而不是单次操作的最坏情况。

• 直觉 (Intuition)：将运行时间类比为金钱（Credits），即 Time = Money。
• 核心思想 (Key Idea)：
  • 廉价操作：支付高于实际成本的费用，将多余部分存入“口袋（Pocket/Credits）”中。
  • 昂贵操作：利用之前存储的信用额度（Credits）来支付其高昂的实际成本，而不需要额外拨款。

2. 记账逻辑：银行与口袋

在记账法中，我们通过设定“均摊成本（Amortized Cost/Bank Loan）”来平衡预算。

概念	含义	作用
实际成本 (Actual Cost)	算法操作真正消耗的时间。	真实支出的钱。
均摊成本 (Bank Loan)	我们为每次操作预设的固定预算。	我们的“最坏打算”，用来覆盖昂贵操作。
存款 (Pocket/Credits)	均摊成本与实际成本的差额。	我们对昂贵操作很少发生的“均摊希望”。

核心等式：

$$\text{总实际成本} = \text{银行借款总额 (均摊总成本)} - \text{口袋剩余存款}$$

只要口袋剩余存款 $\ge 0$，我们设定的均摊成本就是有效的上界。

---

3. 经典案例：二进制计数器 (Binary Counter)

对一个 $k$ 位的二进制计数器执行 $n$ 次递增（Increment）操作。

3.1 成本模型

• 实际成本：翻转的比特位数量。
• 最坏情况：单次操作可能翻转 $k$ 位（如 011...1 $\to$ 100...0），总复杂度看起来是 $O(nk)$。

3.2 记账法证明（均摊 $O(1)$）

• 操作分配：
  • $0 \to 1$ (设置位)：分配 2 均摊成本。1 用于当前支付，1 存入该位。
  • $1 \to 0$ (重置位)：分配 0 均摊成本。直接从该位之前存入的 1 中支取。
• 结论：
  • 每次 Increment 操作只有一个 $0 \to 1$ 的翻转，因此每次只需从银行借 2。
  • $n$ 次操作总成本 $\le 2n$。
  • 均摊成本为 $O(1)$，总复杂度为 $O(n)$。

---

4. 常见误区：均摊 vs 平均

很多同学会将均摊分析与平均复杂度混淆，其本质区别如下：

• 均摊分析 (Amortized)：不涉及概率。它是对最坏情况序列的绝对保证。只要操作序列够长，昂贵操作的影响就会被稀释。
• 平均情况分析 (Average-case)：依赖概率分布。假设输入是随机的，计算期望值。如果输入不随机，结论可能失效。

---

5. 总结：Aesop’s Moral (寓言启示)

• Bank (银行)：是我们对昂贵操作的最坏预期（Worst-case outlook）。
• Pocket (口袋)：是我们对昂贵操作稀少发生的均摊希望（Amortized hope）。