從一個全域平均到逐操作的預算
上一篇給了你聚合法：把整個 n 個操作序列的真實成本加總，除以 n，把結果稱為每個操作的攤還成本。它管用，而且對單一方法的分析來說常是最快的路。但它有個讓你心裡發毛的弱點——你得先為「總和」找到一個漂亮的封閉形式，才能學到任何逐操作的東西，而當好幾種不同操作交錯出現時，那個總和會變得很彆扭。記帳法（又叫銀行家法）把順序顛倒過來：它不先加總、最後再除，而是預先給每個操作一個固定的價格，並證明帳本永不出現赤字。
核心訣竅一句話就能說完。你可以「發明」每一種操作的收費——稱為該操作的攤還成本——它可以高於或低於該操作真正的花費。當你收得比真實成本多，多出來的並沒有浪費：你想像把它當成存款存在資料結構的某處，像是擺在你剛碰過的物件上的預付硬幣。當某個操作真正的花費超過你對它的收費，它就從先前操作已經存下的存款裡支付差額。只要你能保證存款餘額永不掉到零以下，那麼你那些發明出來的收費之和，就是真實總和的一個誠實上界——而每筆收費就是你的攤還成本。
實作範例：多重彈出堆疊
回想本階稍早的多重彈出堆疊。它支援 push（在頂端放一個物件）、pop（移除頂端物件）與 multipop(k)（彈出頂端的 k 個物件，若堆疊不足 k 個就清空）。單次 multipop 可能很昂貴——彈出 k 個物件要花 k 個基本步——所以樸素的逐操作最壞情況是單次呼叫 O(n)，暗示 n 個操作有個會誤導人的嚇人 O(n^2)。聚合法已經證明真相是總共 O(n)。讓我們用記帳法重新導出同一個答案，看看推理會變得多麼「局部」。
指定這些攤還收費：push 收 2，pop 收 0，multipop 收 0。再讀一次——我們在「超收」push，並讓兩種移除都免費。push 多出來的那枚硬幣去了哪裡？想像每個物件從被 push 的那一刻起，就隨身帶著恰好一枚預付硬幣。push 真正花費 1（放置物件）；我們收 2，於是它把 1 花在真正的工作上，留下 1 枚硬幣擱在它剛放下的物件上。那枚硬幣就是這個物件為自己日後被移除而設的託管金。
現在每次移除都用託管金為自己付帳。一次 pop 移除一個物件；它 1 的真實成本由那個物件自被 push 以來一直帶著的那枚硬幣支付，所以我們誠實地對這次 pop 收 0。一次 multipop(k) 移除 k 個物件；這 k 個物件各自仍帶著自己的硬幣，所以全部 k 單位的真實成本都由被花掉的 k 枚硬幣支付——這次操作同樣收 0。關鍵的不變量一目了然：一個物件只能被移除一次，而它總是恰好有它需要的那一枚硬幣，因為它不可能已經被移除過。存款餘額等於堆疊上當前的物件數，這永不為負。所以帳本永遠平衡。
把 n 個操作的攤還收費加總：每個操作至多收 2，所以總攤還成本至多 2n = O(n)。因為存款餘額從未變負，這就是「真實」總工作量的一個貨真價實的上界——所以多重彈出堆疊上的 n 個操作花 O(n) 時間，每個操作的攤還成本是 O(1)。注意我們從不需要找出一個封閉形式的總和；我們只是逐物件檢查了一個局部不變量。
第二個範例：二進位計數器
記帳法在二進位計數器上大放異彩，那裡「硬幣擺在哪裡」的圖像格外鮮明。你有一個以位元儲存的二進位數，唯一的操作是 increment（遞增）：加 1，它把一串尾端的 1 位元翻成 0，然後把一個 0 位元翻成 1。一次遞增可能翻很多位元——從 0111...1 變到 1000...0 會把它們全翻掉——所以單看一次遞增的成本可高達位元數。然而每次遞增的攤還成本是平的 O(1)，而記帳法精確地告訴我們為什麼。
在每個目前為 1 的位元上放一枚存款硬幣。對每次遞增收 2 的攤還成本。記帳之所以成立，是因為一次遞增恰好做兩種位元翻轉，而我們把收費拆開來涵蓋它們。把一個位元從 0 設成 1（每次遞增恰好發生一次）花 1 的真實工作；我們從收費裡支付它，並用遞增的第二枚硬幣去「放一枚存款硬幣」在那個新設的 1 位元上，為它日後被清零的那天預付。把位元從 1 清成 0（一次遞增裡可能發生很多次）則完全由已經擺在那些 1 位元上的硬幣支付——每個被清掉的 1 位元恰好花掉它一直帶著的那枚硬幣。
存款餘額永遠等於計數器中目前 1 位元的數目，這顯然永不為負——你無法從一個已經是 0 的位元上花掉硬幣。所以 n 次遞增總共至多花 2n = O(n)，因此每次攤還 O(1)。這幅圖像就是整個證明：一個 1 位元總是帶著它清掉自己所需的那枚精確硬幣，由當初設下它的那次遞增存入。
increment: i = 0
while bit[i] == 1: # clear a run of 1s, each paid by its stored coin
bit[i] = 0
i = i + 1
bit[i] = 1 # one 0->1, charged + deposit one new coin如何選擇收費（以及如何檢查它們）
記帳法的藝術在於挑選逐操作的收費，而有一個可靠的思考方式。辨認出哪些操作便宜又頻繁、哪些昂貴又罕見。把便宜的那些剛好超收一點點，使得當某個昂貴操作必須執行時，它將碰到的物件早已累積了足以支付它的存款。經典的測試案例是動態陣列加倍：一次附加通常是 O(1)，但那次罕見、觸發複製全部當前元素的附加要花 O(n)。記帳的修法是對每次附加收一個小常數——比方說 3——使每個插入的元素都存下足夠的存款，以便日後在陣列加倍時支付複製自己一次的費用。
- 為每個操作猜一個攤還收費，刻意超收那些便宜又頻繁的操作。
- 決定盈餘存在哪裡——命名存款不變量，例如「堆疊上每個物件一枚硬幣」或「每個 1 位元一枚硬幣」。
- 對每個操作，檢查它能用自己的收費加上已存在它所碰物件上的存款，付清它的真實成本。
- 確認在任何有效序列的任何一點，存款餘額都不會變負。
- 若兩者都成立，收費之和便界定了真實總和，所以每筆收費都是有效的攤還成本。
誠實的界線：攤還 O(1) 承諾什麼、不承諾什麼
把你證明的東西講精確。攤還 O(1) 是對一個序列「總和」的保證，不是對任何單一操作的保證。在動態陣列上，那次觸發加倍的附加（插入）在真實時間裡仍貨真價實地花 O(n)——記帳並沒有讓那個操作變快，它只證明了這類尖峰夠罕見，使長期平均維持常數。若你的應用對每一個別操作有硬性的即時期限（機器人控制迴圈、音訊回呼），攤還上界就是錯誤的工具，因為偶發的昂貴操作即使在平均很小的情況下，仍可能炸掉逐操作的預算。
再給兩個誠實提醒。第一，攤還成本和平均情況成本不是同一回事：攤還是針對「任何」合法序列的最壞情況陳述，對輸入完全不做機率假設；而平均情況則取決於一個假定的輸入分布。攤還上界即使面對一個挑選最惡毒可能序列的對手仍然成立。第二，記帳法與聚合法是同一個記帳現實的兩種視角——當兩者都適用時它們給出相同的攤還成本，你挑哪個讓眼前結構的記帳更乾淨就用哪個。
最後，記帳法有個常常更機械化的姊妹：位勢法，也就是下一篇的主題。記帳法把硬幣灑在個別物件上、要你追蹤它們，而位勢法把所有那些存款打包成單一個數字——整個資料結構狀態的一個位勢函數——並把每個攤還成本算成真實成本加上那個數字的變化量。兩者在數學上等價：總位勢就是帳本上的總存款。先精通記帳法，因為硬幣的圖像讓概念變得具體；之後位勢法會感覺像同一個會計師，從零錢切換到單一的滾動餘額。