均摊分析

动态数组倍增扩容单次 $O(n)$ ，为什么说尾部追加是 $O(1)$ ？哈希表扩容 rehash 全表，为什么插入仍是 $O(1)$ ？答案是均摊分析：不看单次操作的最坏代价，而看一串操作的总代价。

三种方法

直接算 $n$ 次操作的总代价，再除以 $n$ 。

动态数组的例子：从容量 1 开始，追加 $n$ 次。扩容发生在大小达到 $1, 2, 4, \ldots, 2^k$ 时，拷贝总代价为

\sum_{i=0}^{k} 2^i = 2^{k+1} - 1 < 4n \quad (2^k < n),

即 $n$ 次追加总代价 $O(n)$ ，每次均摊 $O(1)$ 。倍增因子的作用在这里看得清楚：2 倍意味着总拷贝不超过 $2n$ ，1.5 倍意味着不超过 $3n$ 但空间浪费更少。

给每个操作多收"费"，存进"银行"支付未来的昂贵操作。动态数组每次追加收 3 个单位：1 个付自己，2 个存着——扩容时每个老元素恰好有 2 个单位付拷贝。只要银行余额永不为负，均摊界就成立。

定义势函数 $\Phi$ （系统的"预付能量"），第 $i$ 次操作的均摊代价为

\hat{c}_i = c_i + \Phi(D_i) - \Phi(D_{i-1}),

即实际代价加上势能变化。若 $\Phi(\text{初始}) = 0$ 且 $\Phi \ge 0$ ，则总均摊代价是总实际代价的上界。动态数组取 $\Phi = 2n - m$ （ $n$ 元素数、 $m$ 容量）可推出同样的 $O(1)$ 。

三种方法是同一件事的三种视角：聚合最直接，记账最直观，势能最一般化（适合复杂的结构如斐波那契堆）。

均摊 $O(1)$ 的意思是总代价 $O(n)$ ，不是每次 $O(1)$ 。单次扩容仍要付 $O(n)$ ——这在两个场景必须显式处理：

实时系统：偶发的 $O(n)$ 停顿不可接受。对策：增量式扩容（每次操作迁移固定数量的元素，把 $O(n)$ 摊到每次操作上，单次最坏 $O(1)$ ）或预分配。
延迟敏感服务：哈希表 rehash 的停顿会打进 p99（→ 性能工程与可观测性）。Redis 的渐进式 rehash 是标准答案（→ 哈希表）。

均摊分析的对象必须是一串操作，且昂贵操作不能被无限触发而不带中间的便宜操作。两个经典结果：

标准库的均摊保证在并发下要小心：动态数组倍增时读者会看到中间状态，因此并发容器要么锁整个结构，要么放弃均摊保证换无锁操作。