摊还分析
摊还分析衡量的是：在一整串操作上，平均每次操作的代价是多少——前提是偶尔一次昂贵的步骤，由许多次便宜的步骤替它分担。最贴近生活的画面是订阅。一本杂志要你一次付清一整年的钱，可感觉上像是每月一小笔开销，因为你把那一大笔费用摊——摊还——到了十二个月里。计算里有些操作正是这样运作：时不时有那么一次干了很多活，但若把这一阵突发的工作量平摊到它周围所有操作上，每次操作的代价就保持得又小又可预测。
经典例子是动态数组（比如 C++ 的 std::vector）。往末尾添加一个元素通常是 O(1)——往下一个空位一放就行。但偶尔数组满了，于是它申请一块更大的内存、把所有东西复制过去，这是一步 O(n)。这听起来吓人，直到你注意到那个倍增模式：一次规模为 n 的复制，只会在自上次复制以来约 n 次便宜的添加之后才发生，所以这些复制在长程上加起来，总量正比于添加的次数。摊开来看，每次添加是 O(1) 摊还——这是一个关于平均的保证，尽管个别的那几次会突然飙高。
为什么要给它单起一个名字？因为「每次操作的最坏情况」可能悲观得误导人。如果你把 vector 的添加报成「最坏 O(n)」，你就会错误地推断出「建一个一百万项的列表是 O(n^2)」；而摊还分析表明，整体其实是 O(n)。请留意它与平均情况分析的细致区别：平均情况是对随机输入取平均，碰上一个坏输入就可能失手；而摊还代价是对那一整串操作的保证，对任何输入都成立。对于那些代价以「罕见、付得起的突发」形式到来的操作，它是诚实的定价方式。
void push_back(int x) {
if (size == cap) { // rare: array is full
cap = (cap == 0) ? 1 : cap*2; // double the capacity
data = grow_and_copy(data, cap); // O(n) this time only
}
data[size++] = x; // usually O(1)
}溢出时翻倍，让大多数 push 是 O(1)；那次罕见的 O(n) 复制，由它之前那些便宜的操作替它买单。
摊还（对整串操作的保证）与平均情况（对随机输入取的平均）不是一回事。动态数组的一次添加是 O(1) 摊还，尽管单独的一次可能是 O(n)。