一個想法：先總和，後平均
上一篇留給我們一個抱怨與一個希望。抱怨是：把單一操作的最壞情況乘以 n，會嚴重地高估，因為那些昂貴的操作不可能同時發生——它們必須輪流上場。希望是：應該存在一種方式，向每個操作收取一個平滑、誠實的價格，加總起來卻仍等於真正的總和。聚合法是兌現這份希望最直接的途徑，而它簡單得幾乎令人不好意思。你不再問「單一操作最壞能花多少？」，而是問「一整段 n 個操作的序列，全部加起來最壞能花多少？」——然後才除以 n。
把它寫成食譜。令 T(n) 是「從空結構出發的任意 n 個操作序列」之總成本的一個緊上界。那麼 聚合法就宣告每個操作的攤還成本為 T(n) 除以 n。注意這裡主張了什麼、又沒主張什麼。每個操作都被指派相同的攤還成本，也就是平均值 T(n)/n。這個平均值在唯一要緊的意義上是誠實的：若你向 n 個操作各收這個金額，這些收費加起來等於 T(n)，而它確實界住了該序列實際的花費。沒有任何記帳花招，沒有逐操作的個案分析——就只是一個總和，除一下。
把二進位計數器整段地數
最乾淨的第一個例子是替一個二進位計數器做遞增，就是上一篇引入的那個結構。你有一個 k 位元的計數器，全為零，並呼叫 increment n 次。一次 increment 的成本，是它執行的位元翻轉次數。單次 increment 可以很便宜——把 ...0 變成 ...1 只翻一個位元——也可以很昂貴——把 0111 變成 1000 時，一串 1 一路進位上去，翻了四個位元。樸素的最壞情況說：每次 increment 最多翻 k 個位元，所以 n 次 increment 要花 O(n k)。沒錯，但很鬆：你不可能每一次都翻 k 個位元，因為長進位鏈只在有一長串 1 等著被清掉時才會發生。
聚合法拒絕一個一個地界定 increment。它改而問：在整段 n 次 increment 裡，總共發生了多少次位元翻轉？把視角從「按操作」換成「按位元位置」。第 0 位元——最低位——每一次 increment 都翻，所以翻了 n 次。第 1 位元翻的頻率是一半，每兩次 increment 翻一次，約 n/2 次。第 2 位元每四次 increment 翻一次，約 n/4 次。一般而言，第 i 位元約翻 n 除以 2^i 次。因此翻轉的總數就是從 i=0 起的 n/2^i 之和，等於 n 乘上幾何級數 (1 + 1/2 + 1/4 + ...)，而那個級數小於 2。
total flips over n increments = (flips of bit 0) + (flips of bit 1) + (flips of bit 2) + ... = n + n/2 + n/4 + n/8 + ... = n * (1 + 1/2 + 1/4 + 1/8 + ...) < n * 2 = 2n amortized cost per increment = total / n < 2n / n = 2 = O(1)
所以 n 次 increment 的真正總成本小於 2n，而不是 n 乘 k。除以 n，每次 increment 的攤還成本小於 2——一個常數，O(1)，與計數器有多寬無關。這是 攤還二進位計數器的頭條結論，並請注意這場勝利來自「對位置求和」而非「對操作取最大」。那些全進位的昂貴 increment 確實存在，但它們稀有到讓便宜的那些綽綽有餘地把它們的帳付清。幾何級數正悄悄地做著這份公平的算術。
Multipop：一段序列只能彈出它推入過的東西
第二個經典是支援 multipop 的堆疊，它教的是同一招的另一種風味。先有一個普通的堆疊，支援 push 與 pop，各花 1。現在加上 multipop(s)：一次呼叫就彈出最上面的 min(s, 目前大小) 個元素。單次 multipop 可以很昂貴——若堆疊裝著一百萬個項目，一次大 s 的 multipop(s) 就能做一百萬單位的工作。所以對一段 n 個操作的序列，樸素的逐操作最壞情況是 O(n^2)：n 個操作，每個可能觸及多達 n 個元素。
聚合法用一個簡單到像作弊的守恆論證繞過了它。每個被彈出的元素——無論是被普通的 pop，還是身為 multipop 的某個犧牲品——都必定在更早的某刻被推入過堆疊。一個元素若中間沒有再次被推入，就不可能被彈出兩次。所以在整段序列中，pop 動作的總數（把 multipop 移除的每個元素都計入）絕不會超過 push 的總數。一段 n 個操作的序列裡，至多有 n 個 push 操作，因此至多有 n 個推入的元素，因此總共至多有 n 個 pop 動作。
加起來：總工作量 =（push 次數）+（pop 動作數）至多是 n + n = 2n，所以任意 n 個操作序列的總和是 O(n)。除以 n，每個操作——push、pop、甚至那嚇人的 multipop——攤還成本都是 O(1)。這個推廣自二進位計數器的教訓是：當你能找到一個全域的記帳恆等式（每個 pop 都對應一個更早的 push），直接替總和封頂時，聚合法就大放異彩，哪怕沒有任何單一操作擁有小的最壞情況。你界定的不是一次 multipop 的成本；你界定的是整段序列在物理上能彈出的總量。
表格倍增：它管用之處，與它吃力之處
聚合法也能料理那個帶動整階的例子：對一個 滿了就倍增的動態陣列做附加。多數的附加是 O(1)——只是把值寫進下一個空格。但當陣列填滿，觸發重新配置的那次附加，必須配置一個雙倍大小的新陣列、並複製每一個既有元素，花費 Theta(目前大小)。那些大量複製的附加，就是罕見的尖峰。要做聚合，把 n 次附加的複製工作加起來：重新配置發生在大小 1、2、4、8、…直到 n，它們執行的複製總計 1 + 2 + 4 + … + n，一個和小於 2n 的幾何級數。
現在把便宜的部分加進來。n 次附加裡，每次也做 O(1) 的基礎工作來寫入它的元素，貢獻 n。所以總和至多是 n（寫入）加上不到 2n（複製），即 O(n)，每次附加的攤還成本是 O(1)。和二進位計數器同樣的幾何級數魔法：倍增讓重新配置隨陣列長大而呈指數級稀有，所以那些罕見的大複製，加總起來不過是線性。這正是為什麼一個可增長陣列能承諾攤還 O(1) 的附加，儘管偶爾會有 Theta(n) 的卡頓。
這個方法真正告訴你的事
退一步，注意這三個例子共有的形狀。每個例子裡，樸素的逐操作最壞情況（最壞情況乘以 n）都鬆了一個實在的倍數——O(n k) 對 O(n)、O(n^2) 對 O(n)——而每個例子裡，對總和做一次全域的計數，就把那份鬆弛溶解掉了。對計數器與陣列是幾何級數；對堆疊是守恆律。聚合法完全沒有改動演算法；它改的是記帳方式，用一個誠實的整段序列總和，取代了悲觀的逐步取最大。
- 固定序列：從空結構出發的 n 個操作，並決定你要數的「成本」是什麼（位元翻轉、元素觸碰、複製）。
- 用一個巧妙的全域計數找出總和 T(n)——對位置求和，或一個守恆論證——而不是把逐操作的最壞情況加起來。
- 驗證 T(n) 對最壞的序列是貨真價實的上界，且不藏任何機率假設——它必須對最具對抗性的操作順序都成立。
- 把攤還成本報為 T(n)/n，並記得它是所有操作共享的一個平的平均，不是逐操作的保證。
最後一個讓攤還推理腳踏實地的誠實檢查。這裡攤還成本 O(1) 是關於總和如何擴展的陳述，與任何漸進上界同一個精神：它隱藏常數、忽略小 n，所以對極短的序列，那些重新配置的尖峰佔了工作的實在比例，「攤還 O(1)」並不承諾每一次早期的附加都是瞬間完成。它真正承諾的——可證明、對最壞情況成立——是：當序列長大，每個操作的平均仍被一個常數界住。這就是聚合法整份的禮物：從單一個總和，得到一個誠實的逐操作價格。下一篇保有同樣的目標，卻用不同方式開帳單，讓便宜的操作預先替它們日後會引發的昂貴操作付款。