攤還分析
攤還分析衡量的是：在一整串操作上，平均每次操作的代價是多少——前提是偶爾一次昂貴的步驟，由許多次便宜的步驟替它分擔。最貼近生活的畫面是訂閱。一本雜誌要你一次付清一整年的錢，可感覺上像是每月一小筆開銷，因為你把那一大筆費用攤——攤還——到了十二個月裡。計算裡有些操作正是這樣運作：時不時有那麼一次幹了很多活，但若把這一陣突發的工作量平攤到它周圍所有操作上，每次操作的代價就保持得又小又可預測。
經典例子是動態陣列（比如 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)。