本階把我們帶到了哪裡
你來到這裡時已有裝備。第一篇說明了為何向每次操作收取它個人的最壞情況會多算——一個昂貴的步驟，常常是由那些必須先發生的便宜步驟付清的，所以當操作成串到來時，單一操作的最壞情況是錯誤的計價單位。接下來三篇給了你三種誠實地把成本攤開的方法：聚合法（先界定整段序列，再除）、記帳法（向便宜的操作多收費，把盈餘存成存款），以及位勢法（為資料結構的狀態定義一個儲蓄帳戶 Phi，讓 Phi 的差額為尖峰付款）。最後這一篇要把它們花掉。我們取兩個典範案例研究，看著每種方法結清同一筆帳，於是這些方法不再是公式，而成為一種看世界的方式。
把本階開頭那個核心的誠實擺在眼前。攤還 O(1) 是一段操作序列上的平均成本，而非對任何單一操作的承諾。有些附加操作真的會花 Theta(n) 的時間；有些並查集查詢真的會走過一條長路徑。攤還分析保證這類尖峰夠稀少，使得總和除以操作數仍維持很小。對「吞吐量」而言，這是個真實且有用的保證——但若你需要「每一個」個別操作都快（一個即時截止期限、一個互動式畫面更新預算），單靠攤還界限救不了你。我們會明確指出這個區別在哪裡咬人。
表格倍增：平均每次附加 O(1) 的可成長陣列
問題如下。固定陣列有固定容量，但我們想要一個可以一直附加、永遠不必先宣告最終大小的串列。當陣列填滿，唯一的動作就是配置一塊更大的記憶體並把全部內容複製過去。真正關鍵的決定是「大多少」。致勝規則是表格倍增：滿了就配置一個容量加倍的新陣列、複製舊內容、然後繼續。單次附加通常微不足道——寫一格、O(1)——但觸發重新配置的那次附加，要複製當前全部 n 個元素，花 Theta(n)。把那個最壞情況算給每一次附加，會說每次附加都是 Theta(n)，於是 n 次附加花 Theta(n^2)。那正是本階警告過的多算，而且是錯的。真相是 n 次附加總共花 Theta(n)，所以每次是攤還 O(1)。
讓聚合法用最乾淨的方式證明它：先界定整段序列，再除。從空的開始做 n 次附加。便宜的部分——每次附加寫一格——加起來恰好是 n。昂貴的部分是那些複製。重新配置發生在大小 1、2、4、8、……一直到 n，而容量 2^k 處的複製搬動 2^k 個元素。所以複製的總工作量是 1 + 2 + 4 + … 直到 n，一個小於 2n 的等比級數和。總工作量至多是 n + 2n = 3n = Theta(n)。除以 n 次操作：每次附加攤還 O(1)。那個等比級數就是全部的祕密——加倍讓每次重新配置比上一次貴一倍，但也稀少一倍，而那些稀少卻巨大的項，坍縮成 n 的一個小常數倍。
copy work = 1 + 2 + 4 + ... + n/2 + n
= sum of 2^k for k=0..log2(n)
< 2n (geometric series)
total = n (writes) + 2n (copies) = Theta(n)
amortized = Theta(n) / n = O(1) per append同一筆帳，用存款與用位勢來付
現在用記帳法付這張一模一樣的帳單，對倍增而言它往往最直觀。向每次附加收取固定的攤還費 3 單位。其中 1 單位支付當下實際發生的那次寫格。另外 2 單位被存成存款，擱在這個剛加入的元素身上。為何是 2？因為當陣列下次從大小 m 加倍到 2m，那 m 個元素每個都得被複製，而我們需要一個單位準備好支付那次複製。乾淨的記帳如下：在一次重新配置與下一次之間，陣列從 m 成長到 2m，所以有 m 個全新元素到來，每個帶著 2 個存起來的單位——那是存進 2m 單位。那次重新配置複製 2m 個元素（m 個舊的加 m 個新的），每個 1 單位。那 2m 個存起來的單位恰好支付 2m 次複製。帳戶從不變負，所以攤還費 3 成立，而 3 = O(1)。
位勢法用一個數字、而非逐元素的存款，講同一個故事。定義一個位勢 Phi：它在剛重新配置後是 0，隨陣列填滿而成長，在下次重新配置前達到頂峰，好讓它釋放出剛好足夠支付複製的量。一個標準選擇是 Phi = 2 * 元素數 - 容量。檢查看看：剛重新配置後，陣列半滿（元素數 = 容量/2），所以 Phi = 2*(容量/2) - 容量 = 0。下次重新配置前，陣列全滿（元素數 = 容量），所以 Phi = 2*容量 - 容量 = 容量，充飽。一次普通附加讓元素數加 1，於是 Phi 升 2，攤還成本 = 實際 1 + 2 = 3。一次觸發重配的附加做了「容量」這麼多的實際工作（複製），但 Phi 從容量崩回 0、降了容量，所以攤還成本 = 容量 + 1 - 容量 +（少許）= O(1)。同樣的常數，從單一狀態函數推出——這正是把 Phi 選好給你的回報。
一個姊妹例子，與一道誠實的疤痕
同樣的等比魔法驅動著二進位計數器：把一個 k 位元的計數器從零開始遞增 n 次，雖然單次遞增可能翻動每個位元（想想 0111 -> 1000），聚合帳單卻很小。第 0 位元每次遞增都翻（n 次）、第 1 位元每隔一次翻（n/2）、第 2 位元每隔四次翻（n/4），依此類推——一個加總到小於 2n 次翻動的等比級數。所以每次遞增攤還 O(1)，即使最壞的單次遞增是 Theta(k)。記帳觀點同樣俐落：設定一個位元付 2 單位（1 個現在設定，1 個存在它身上以支付終將到來的清除），於是清除就免費了。這跟表格倍增是一模一樣的記帳把戲，只是換了身衣裳。
現在來談那道疤，因為它是真的。表格倍增的 O(1) 是攤還的，而最壞的單次附加仍會以 Theta(n) 的時間複製整個陣列。若那 n 個元素是每秒被附加 60 次的視訊畫面，偶爾那次 Theta(n) 的複製就是一個看得見的卡頓——一個錯過截止期限的畫面——即使每次附加的「平均」微乎其微。吞吐量極佳；最壞情況延遲則否。需要有界的每次操作時間的工程師會用不同的設計（漸進式重新配置：每次普通附加複製幾個舊元素，把工作攤開，使得沒有任何單一附加要付整筆複製）。這個課題正是本階的頭條誠實：攤還界限是對一段「序列」的保證，從來不是對每次操作的承諾。
並查集：當攤還近乎常數
第二個案例研究更宏大。一個不相交集合（並查集）結構維護把物件分組的一個劃分，並支援兩種操作：find(x) 回傳 x 所在群組的一個代表，union(x, y) 合併兩個群組。標準實作是一座森林：每個物件指向一個父節點，而一棵樹的根就是代表。天真地做，find 會沿著父指標往上走到根，而草率的 union 能建出一條長鏈、使 find 變慢——最壞情況 Theta(n)。兩個小巧的啟發法合起來戲劇性地修好它。其一，按秩合併：合併時把較矮的樹掛在較高的樹下（秩近似高度），這讓樹維持淺。其二，路徑壓縮：每次 find 從 x 往上走到根，就把它經過的每個節點直接指向根，於是這些節點未來的 find 瞬間完成。
- find(x)：從 x 沿父指標往上走到根 r；那就是代表。
- 路徑壓縮：回程時，把 x 與經過的每個節點都重新指向 r，把樹壓平。
- union(x, y)：找出兩個根；若不同，把秩較低的根接到秩較高的根之下（按秩合併）。
- 秩相同時，任選一個根當新的父節點，並把它的秩加一。
攤還分析交出什麼？單用按秩合併，每次操作是 O(log n)。單用路徑壓縮，也不錯。兩者「合用」時，一個著名而困難的定理（歸功於 Tarjan）證明：對 n 個物件做 m 次操作的序列，總時間是 O(m * alpha(n))，其中 alpha 是反阿克曼函數。誠實而精確的陳述是：alpha(n) 成長得如此緩慢，以致於對每一個能在這宇宙裡寫得下的 n，它至多是 4 或 5。所以每次操作的攤還成本「並非」字面上的 O(1)——alpha(n) 嚴格說來確實會成長——但它如此接近常數，以致沒有任何現實輸入感覺得到差別。這是全演算法領域最著名的「實際上是常數」的界限，而要得到它必須結合那些啟發法；單獨任一個都搆不著。
兩個警告，以及攤還分析不是什麼
第一個警告：別把攤還成本與平均情況成本搞混。平均情況時間依賴一個假設的輸入分布——它回答「在一個『隨機』輸入上有多快？」，而若你的輸入並非隨機就會改變。攤還成本對輸入分布「不」做任何假設；它是對任意序列之「總和」的最壞情況保證，然後除以次數。表格倍增與並查集的界限對「敵對」輸入也成立，是世界能塞給你的最壞情況，全程沒有任何機率。那是一種嚴格強於平均情況的承諾，而兩者只會偶然重合。把它們放進心裡不同的盒子。
第二個警告：攤還界限描述的是縮放，而大O符號仍隱藏常數。每次附加 3 單位的費用、以及那個小小的 alpha(n) 都是貨真價實的，但在真實機器上，藏在 O(1) 裡的那個「常數」——快取行為、配置器成本、指標追逐——才決定在給定大小下哪個結構勝出。對小的 n，一個樸素的過量配置陣列勝過任何花俏東西；並查集的啟發法只在 n 與 m 都大時才值回票價。一如既往，漸進告訴你成本如何成長，而非在 n = 50 時誰贏。要緊時就量測。
退後一步看見那份統一。表格倍增、二進位計數器與並查集看似三個不相干的把戲，但每一個都是本階那「單一想法」的化裝：一個偶發的昂貴操作，由它周遭眾多便宜的操作預先付清，使得整段序列上的攤還成本維持很小。等比級數為倍增與計數器辦到了這件事；一個深刻的樹壓平論證為並查集辦到了。而這些結果中的每一個，都能透過全部三副眼鏡——聚合、記帳、位勢——來閱讀，因為它們不是三套理論，而是為同一個真實成本記帳的三種誠實方式。