复杂度的均摊分析法
- 动态数组的尾插
push_back，有时会触发扩容； - 一旦扩容，就要申请更大的内存、搬运旧元素、再插入新元素。某一次操作的代价完全可能是 O(n)O(n)
- 但是，动态数组尾插的复杂度是均摊 O(1)O(1)
类似的现象其实非常多：单看某一次操作，它们都可能很贵；但把它们放到足够长的操作序列里，平均到每一步，复杂度却仍然很低。均摊分析研究的正是这种现象。
平均情况分析 vs 均摊分析
均摊分析和平均情况分析（average-case analysis）不是同一个概念。
平均情况分析通常要假设输入服从某种概率分布，然后计算期望成本。比如快速排序的平均复杂度分析，核心就在于对输入或主元分布做假设。例如，快速排序平均是 O(nlogn)O(nlogn) 的，但最坏可能是平方复杂度。
均摊分析则不同。它不依赖概率和输入，一个 vector 无论怎样尾插，均摊复杂度也是 O(1)O(1) 。
我们可以定义：对于一个数据结构的一段操作序列
σ=(o1,o2,…,om),σ=(o1,o2,…,om),
如果总实际成本是
C(σ)=∑i=1mci,C(σ)=i=1∑mci,
能否证明存在某个函数 f(m)f(m)，使得
C(σ)≤m⋅f(m)。C(σ)≤m⋅f(m)。
如果可以，那么就说这类操作的均摊复杂度是 f(m)f(m)。可以理解为，均摊分析给出的是“整段序列的总账不贵”的承诺。于是，均摊 O(1)O(1) 并不意味着每次操作都只花常数时间，它真正的含义是：在任意长的合法操作序列里，总成本相比操作次数的复杂度没有那么高。
经典例子：动态数组
动态数组是本文最好的主线。假设一个动态数组有两个状态量：
size：当前元素个数capacity：当前容量
执行push_back(x)时：
- 若
size < capacity，直接写入，成本记为 11； - 若
size = capacity，则申请一个两倍大的新数组，把旧元素全部搬过去，再插入新元素。若旧容量为 kk，那么这次成本记为 k+1k+1。
单次最坏显然是线性的；但长期看却是均摊常数。下面分别用三种方法来理解它。
聚合法：直接算前 nn 次操作的总成本
聚合法直接计算多步的总成本。由于每次扩容是两倍，数组容量会按 1,2,4,8,…1,2,4,8,… 这样翻倍增长。做完前 nn 次插入时，普通写入本身一共发生了 nn 次，成本是 nn。除此之外，还会发生若干次扩容搬运，搬运量依次是 1+2+4+⋯+2k−1,1+2+4+⋯+2k−1,，其中 2k−1<n≤2k2k−1<n≤2k 。于是
1+2+4+⋯+2k−1<2k≤2n。1+2+4+⋯+2k−1<2k≤2n。
所以总成本满足
C(n)≤n+2n=3n。C(n)≤n+2n=3n。
也就是说，前 nn 次push_back的总成本是 O(n)O(n)，因此平均到每次操作，复杂度就是 O(1)O(1)。
这个证明非常重要，因为它第一次把“偶尔很贵”和“长期很便宜”这两个看似矛盾的结论接起来了。扩容确实贵，但扩容发生得足够稀疏，所以总账仍然可控。
记账法：平时多收一点，留着给扩容买单
记账法比聚合法更有“预算”的味道。我们不直接算总账，而是假装给每次操作都规定一个均摊收费标准。
还是看动态数组尾插。设每次push_back都收费常数代价 33。
- 如果这次没有扩容，真实成本只有 11，那就剩下 22 存起来；
- 如果这次触发扩容，就从之前存下来的余额里支付搬运成本。
为什么这个方案可行？考虑一次从容量 mm 扩到 2m2m 的扩容。在这次扩容发生前，数组已经经历了从半满到装满的一系列普通插入。也就是说，每次扩容时，前面都有发生了足够多（大约 m/2m/2 ）的便宜插入，每次都能攒出足够余额，总共可以积累出足以覆盖这次搬运的资金。
势能法
从记账的思想更进一步，我们就可以引出势能法。它的思想是：给数据结构状态 DiDi 定义一个势能函数 Φ(Di)Φ(Di)，然后把第 ii 次操作的均摊成本定义为
c^i=ci+Φ(Di)−Φ(Di−1)。c^i=ci+Φ(Di)−Φ(Di−1)。
这里：
- cici 是第 ii 次操作的真实成本；
- c^ic^i 是我们定义出来的均摊成本；
- Φ(Di)−Φ(Di−1)Φ(Di)−Φ(Di−1) 表示状态势能的变化。
这样一次操作的均摊成本就是他的"实际成本 + 势能变化"
如果我们能选取出合适的势能函数表示当前状态（要保证势能始终非负，并且初始势能为 00），那么对前 mm 次操作有
∑i=1mc^i=∑i=1mci+Φ(Dm)−Φ(D0)≥∑i=1mci。i=1∑mc^i=i=1∑mci+Φ(Dm)−Φ(D0)≥i=1∑mci。
所以，只要每一步的均摊成本都有常数上界，那么真实总代价也就有同阶上界。
对动态数组，一个经典势能函数是
Φ=2⋅size−capacity。Φ=2⋅size−capacity。
这个定义的直觉是：数组越接近装满，也就越接近下一次扩容，势能越大。
对于不扩容的普通插入。真实成本 1，势能变化 2（因为size增加 1，而capacity不变），均摊代价 3
对于触发扩容的插入。插入前size = m，capacity = m，势能是 Φold=mΦold=m；插入后size = m+1，capacity = 2m，势能变成
Φnew=2(m+1)−2m=2。Φnew=2(m+1)−2m=2。
这次真实成本是搬运 mm 个旧元素再插入新元素（共 m+1m+1），势能变化是 ΔΦ=2−m。ΔΦ=2−m。。所以均摊成本为 33
不扩容时是 33，扩容时还是 33。因此动态数组尾插的均摊复杂度就是 O(1)O(1)。
其他常见例子
栈的MULTIPOP
考虑一个支持三种操作的栈：
PUSH(x)：压栈，成本为 11；POP()：弹栈，成本为 11；MULTIPOP(k)：连续弹出最多 kk 个元素，成本等于实际弹出的元素数。
单看一次MULTIPOP(k)，它当然可能要弹很多元素，代价不是常数。但如果看一整段操作序列，总弹出次数其实不可能超过总压栈次数。因为每个元素最多只会被压入一次、弹出一次。
因此，如果总共有 mm 次操作，那么所有弹栈动作加起来不会超过线性级别，于是总成本是 O(m)O(m)，均摊每次仍是 O(1)O(1)。
这个例子特别适合作为均摊分析的第一个训练：只要能发现“每个元素最多被贵处理一次”，总成本往往就很好控制。
二进制计数器的自增
再看一个更经典的例子。一个二进制计数器不断执行INCREMENT，一次操作的成本定义为被翻转的位数。