一張幾乎總是很小、偶爾巨大的帳單
到了這個階段，你已能讀一段程式碼、數出它的迴圈迭代次數，並用大O界報出一個最壞情況執行時間。這個習慣通常完全正確。但它有一個盲點，會在我們分析「一個被連續使用許多次的資料結構」、而非「一個只跑一次的演算法」時冒出來。想想往一個可成長陣列（Python 的 list、Java 的 ArrayList、C++ 的 vector）尾端附加元素。幾乎每一次附加都只是寫進一個槽位然後返回——成本 1。但偶爾陣列滿了，附加就得配置一塊更大的記憶體、把全部元素搬過去——成本與當前大小 n 成正比。
現在問一個自然的問題：一次附加的最壞情況成本是多少？誠實的答案是 Theta(n)，因為下一次呼叫說不定恰好就是觸發整體複製的那一次。所以若你像分析任何單一操作那樣分析附加——取它的最壞情況——你會得出 n 次附加最多花 n 乘以 Theta(n) = Theta(n^2)。這個界是真的，卻也鬆得離譜。從空陣列做 n 次附加的真實成本是 Theta(n)，而非 Theta(n^2)。每次操作取最壞情況，整整高估了一個 n 的倍數。釐清「為什麼」，以及「如何改為得到誠實的 Theta(n)」，正是這一整階的工作。
高估從何而來：最壞情況不可能全部發生
「n 次附加最多花 n 乘以最壞的單次附加」這句話的破綻，藏在一個看似無辜的詞裡：每一次。那個界悄悄假設了每個操作都能同時撞上自己的最壞情況。對於一次性的演算法這沒問題——最壞的輸入確實能讓一個迴圈跑滿全程。但對於在共享結構上的一序列操作，這些操作並不互相獨立。昂貴的複製只在陣列滿了時才發生，而陣列之所以會滿，正是因為許多便宜的附加剛把它填滿了。讓某個操作變貴的那些條件，恰恰就是保證它周圍的鄰居很便宜的那些條件。
用一個倍增陣列把它變得鮮活。從空的、容量 1 開始。複製發生在大小 1、2、4、8、16、… 時，每次約花那麼多次元素搬移；其間每次附加成本都是 1。在 n 次附加中，複製的總成本約為 1 + 2 + 4 + … 直到 n，這個等比和加起來不到 2n——而便宜的附加再添一個 n。總計：不到 3n 次搬移，也就是 Theta(n)。昂貴的複製是真實存在的，但它們既稀少、又相對於買下它們的便宜工作量而言不斷縮小：一次大小為 n 的複製，唯有在 n 次便宜附加付清入場費之後才可能發生。根本不存在一種序列能讓每次附加都是那個昂貴的。
「攤還成本」到底是什麼意思
定義來了，而且接地氣得令人舒坦。一個操作的攤還成本是我們指派給它的一個數字，使得對每一條操作序列，這些攤還成本的總和都是真實成本總和的一個上界。我們說某結構的附加是攤還 O(1)，意思是任何 m 次附加序列的真實總成本至多為 O(m)——等價地說，平攤到整段序列上的成本被一個常數所界。倍增陣列就是攤還 O(1)：我們剛看到任何 n 次附加都不到 3n，所以每次附加收 3 是個完全站得住腳的攤還計費。
兩個重點讓這份定義保持誠實。第一，攤還成本是某個序列加總的性質，由我們選定的記帳方案所確立，而非某個孤立操作自帶的魔法屬性。第二，這個界必須對最壞的可能序列都成立——這裡沒有任何機率成分，不對「哪些操作較可能發生」做任何假設。這個分別重要到後面會有專篇來談；現在只要先握住這層對比：攤還分析仍然是一個最壞情況的保證，它只是不再假裝那些最壞情況會疊加起來。
三種記帳的方式
證明攤還界有三種標準技巧，這一階其餘部分各給一篇。它們永遠得到相同的真實總成本——它們是觀照同一現實的不同透鏡，而非互相競爭的主張——所以你挑哪個最容易論證某個問題就用哪個。聚合法最直接：把 n 個操作的總成本當成一個整體來界（正是我們對倍增做的等比和論證），再除以 n 得到每次操作的攤還成本。當總和容易加、且每個操作分到相同攤還計費時，它非常好用。
記帳法（銀行家法）讓不同操作背負不同的攤還計費。你對便宜的操作多收一點，把盈餘當作存款（credit）存在結構上；之後，某個昂貴操作就花掉這筆存起來的存款替自己買單。只要帳戶餘額永不為負，這些攤還計費就可證明地涵蓋所有真實成本。位勢法（物理學家法）用一條公式而非散落的硬幣做同一件事：你定義一個位勢函數 Phi，把結構的每個狀態對應到一個數字（想成「儲存的能量」或「眼下有多亂」），而一個操作的攤還成本就是它的真實成本，加上它造成的 Phi 變化量。讓結構變亂的便宜步驟是在預付；把結構整理乾淨的昂貴步驟則釋放儲存的位勢來支付自己的帳單。
amortized(op) = true_cost(op) + Phi(state_after) - Phi(state_before) sum over the sequence: sum amortized = sum true_cost + Phi(final) - Phi(initial) so if Phi(final) >= Phi(initial) (and usually Phi >= 0, Phi(initial) = 0): sum true_cost <= sum amortized
這一階將要掙得的案例研究
三個經典範例會貫穿全程，現在先見過它們，你就明白這些方法為何值得學。表格倍增就是我們上面用過的那個：n 次附加在 Theta(n) 內完成，故每次攤還 O(1)，這正是為什麼儘管偶有重新配置，「就往 list 附加」仍是日常裡安全的一招。二進位計數器更乾淨俐落：把一個二進位數加一，有時只翻一個位元、有時卻沿著許多位元串起一長串進位，然而從零起算的 n 次遞增中，位元翻轉的總次數不到 2n——每次遞增攤還 O(1) 次翻轉，因為第 i 個位元每 2^i 次遞增才翻一次。
最深刻的案例是帶路徑壓縮與按秩合併的並查集，你在 Kruskal 的最小生成樹演算法裡早已當作引擎見過它。在那裡，一序列 m 個操作的總時間幾近線性——O(m 乘以 alpha(n))，其中 alpha 是反阿克曼函數，一個成長慢到對任何你存得下的 n 都小於 5 的量。就單一操作而言，最壞情況確實比常數更糟，但攤還到整段序列上，每個操作實質上就是常數。這個界是整個演算法分析中最令人驚訝的結果之一，而它純粹是攤還推理——沒有更快的「逐次操作」說法可講。
攤還是最壞情況下的平均，不是機率下的平均
有一個混淆值得立刻擋下，因為「平均」這個詞偷偷溜進了兩種概念裡。攤還分析不是平均情況分析。平均情況時間是對一個輸入的機率分布取平均——它問的是「若輸入以某某方式隨機，期望成本是多少？」——而它的答案，只在那個分布假設可信的程度上才可信。攤還成本則是對一段序列裡的操作取平均，沒有任何隨機性：倍增陣列對一個對手能挑出的單一最壞序列都是攤還 O(1)，而不只是對一個典型序列。
把這個保證的三角形理清楚，因為它們回答的是不同的問題。每次操作的最壞情況是最強的承諾，但如我們所見，它對一段序列可能高估得離譜。攤還把逐次操作的承諾鬆綁成逐序列的承諾，從而救回誠實的總和，且仍不帶任何機率假設。平均情況與期望（如在隨機演算法中，其隨機性住在演算法裡而非輸入裡）則用最壞情況這面盾牌，換取關於隨機性的假設。接下來四篇指南會把這條攤還的中間道路完整建起——聚合的求和、銀行家的存款、物理學家的位勢，以及三種透鏡彼此吻合的表格倍增與並查集案例研究。