元数据卡
- 前置知识：ch14-greedy（复杂度直觉）
- 预计时间：25 分钟
- 核心难度：进阶
- 完成标志：能用三种方法解释"为什么 ArrayList 的 add 是摊销 O(1)"
你的进度
上一站你走进了复杂度暗区——有些问题根本没法快。这章恰好相反：有些操作最坏情况很慢，但放在更大的时间窗口里看，其实很快。你每天用的 list.append 就是如此。可选深入，不影响主线。
你的任务 学会三种摊还分析方法：聚合分析、记账法、势能法。用动态数组扩容解释每种方法。
动态数组扩容
动态数组满了之后，需要分配 2 倍空间并把旧数据誊抄过去。一万条记录、每条几微秒等于几百毫秒。但大多数 append 是 O(1)，你不能因为"偶尔慢一次"就抛弃它。
python
class DynamicArray:
def __init__(self):
self.arr = [None]; self.cap = 1; self.size = 0
def append(self, val):
if self.size == self.cap:
self.cap *= 2
new = [None] * self.cap
for i in range(len(self.arr)):
new[i] = self.arr[i]
self.arr = new
self.arr[self.size] = val
self.size += 1
# 运行: python3 dynarr.py方法 1：聚合分析
总代价除以操作次数。初始容量 1，每次翻倍，n 次插入总代价约 n + (1+2+4+...+n/2) = 2n。平均 O(1)。
方法 2：记账法
每次插入预收摊还代价 3。普通插入（实际=1）存 2 信用；扩容时（实际=旧容量+1）消费信用。余额始终非负。
python
def accounting(n):
cap, bal = 1, 0
for i in range(1, n+1):
amortized = 3
if i > cap:
actual = cap + 1; cap *= 2
else:
actual = 1
bal += amortized - actual
print(f"余额={bal} (应>=0)")
accounting(16)
# 预期: 余额始终为正方法 3：势能法
定义势能 Phi = 2*size - capacity。摊还代价 = 实际代价 + Phi_new - Phi_old。
扩容时：实际=capacity+1, Phi_new-Phi_old=2-(capacity) => 摊还=3。不扩容时：摊还=3。无论是否扩容都是 3。
python
def potential(n):
size, cap, phi = 0, 1, 0
for i in range(1, n+1):
prev = phi
if size == cap:
actual = cap + 1; cap *= 2
phi = 2 * (size + 1) - cap
else:
actual = 1
phi = 2 * (size + 1) - cap
size += 1
amortized = actual + phi - prev
if i <= 3 or i == n:
print(f"size={size}: 实际={actual} 摊还={amortized}")
potential(16)
# 扩容和不扩容摊还都是 3案例：二进制计数器
从 0 递增到 n，总翻转次数永远 = 2n - 1，摊还 O(1)。
python
def count_flips(n):
total = 0
for i in range(1, n+1):
total += (i & -i).bit_length()
return total
for n in [1,2,4,8,16,32,64]:
f = count_flips(n)
print(f"n={n:4d}: 总翻转={f:5d} 均摊={f/n:.4f}")
# 均摊趋近于 2速查表
| 数据结构 | 摊还代价 | 方法 |
|---|---|---|
| 动态数组 push_back | O(1) | 聚合/记账/势能 |
| 二进制计数器 INCREMENT | O(1) | 聚合（总翻转=2n-1） |
| 并查集 find（双优化） | O(alpha(n)) | 势能法 |
| splay 树操作 | O(log n) | 势能法 |
常见陷阱
| 卡点 | 真相 |
|---|---|
| "摊还=平均情况分析" | 不对。摊还是对全部操作取平均，不假设输入分布 |
| "摊还 O(1)=每次 O(1)" | 错。某些操作可能很慢，但被快的次数稀释 |
| "信用值随便定" | 必须数学证明余额永不至负 |
通关挑战
一个栈，支持 push（O(1)）和 multipop(k)（O(k)）。用势能法证明：连续 n 次操作摊还 O(1)。提示：势能 = 栈中元素数量。
旅人笔记
你能向非技术人员解释"最坏 200ms，但平均每次 1 微秒"时，摊还就在帮你说真话。面试中能流利解释"为什么 ArrayList.add 是 O(1)"，面试官知道你不仅会用还懂原理。
下一步：高级数据结构
下一站，拿着这把新武器去面对布隆过滤器、并查集、线段树、Trie 这些更复杂的数据结构。