從散落的硬幣到單一數字
在上一篇指南裡，記帳法讓你對便宜的操作超收費用，再把盈餘當成一枚枚小硬幣，擱在個別元素上——堆疊的每個項目放一枚硬幣，準備好支付它日後被彈出的代價。這做法很漂亮，但它要求你追蹤每一枚硬幣住在哪裡，一旦結構變大、或存款四處移動，就變得繁瑣。位勢法是同一問題的物理學家答案：別把硬幣撒在結構各處，而是把整份存款摺疊成一個單一數字，也就是位勢，記作 Phi（希臘字母 phi）。Phi 是整個資料結構當前狀態的函數，代表「此刻這個結構內部預付了多少功」。
賦予這套方法名字的類比是能量。舉起一個重物，你做了實實在在的功；那份功並未消失，而是以位能的形式儲存在被舉高的重物裡，等著日後釋放。資料結構的操作也一樣。有時你做的功多於一個操作所「應得」的，盈餘就被儲存起來——Phi 上升。有時你把那份儲存的功兌現，去支付一次昂貴的操作——Phi 下降，而它的跌幅幫忙付了帳。精妙之處在於：你從來不必說是哪個元素持有這份能量；你只需為結構的每一種可能狀態指定一個誠實的數字。
驅動一切的那一條定義
整部機器只有一行。把結構的狀態編號，D_0 是起始狀態、D_i 是第 i 次操作後的狀態。令 c_i 為第 i 次操作的真實成本。那麼該操作的攤還成本就定義為：它的真實成本，加上它造成的位勢變化：
amortized cost a_i = c_i + ( Phi(D_i) - Phi(D_{i-1}) )
sum of a_i = sum of c_i + ( Phi(D_n) - Phi(D_0) ) <- telescopes!現在看看這為什麼有價值。把整串 n 個操作的攤還成本加起來。那些位勢差構成一個伸縮和：Phi(D_1) - Phi(D_0)、接著 Phi(D_2) - Phi(D_1)、再 Phi(D_3) - Phi(D_2)，依此類推。每一個中間的 Phi 都出現一次正號、一次負號，於是它們連鎖地全部抵銷，只留下 Phi(D_n) - Phi(D_0)。這就是全部的把戲：攤還成本之和，等於真實成本之和，再加上從頭到尾位勢的淨變化。只要你安排好讓位勢結束時不低於它開始時，那麼攤還成本之和就是真實成本之和的一個誠實上界——而那正是你想界定的總執行時間。
讓你保持誠實的兩條規則
位勢函數不是你想取什麼就取什麼——那會讓你把成本藏進一個暗地裡變負的數字裡，從而證出假的界。兩個條件讓帳目保持誠實，而它們正是讓那個伸縮論證交出真界、而非自我安慰幻覺的條件。
- 從零開始（或把基準訂在那裡）：Phi(D_0) = 0。你以一個空帳戶起步——第一次操作之前不存在任何預付的功。這只是帳務上的方便；你也可以從更高處起步，只要記得在最後把 Phi(D_0) 減掉。
- 永遠不負債：對每一個達到的狀態都有 Phi(D_i) >= 0。帳戶餘額永遠不能為負，因為你不可能花掉一筆從未存入的預付功。這是承重的條件。若它成立，則 Phi(D_n) - Phi(D_0) >= 0，於是真實成本之和至多等於攤還成本之和——這個界是真的。
- 界定每一個攤還成本：證明對每一個操作——無論便宜或昂貴——a_i = c_i + Phi(D_i) - Phi(D_{i-1}) 都很小（常是 O(1) 或 O(log n)）。重點正在於：一個昂貴的操作，其 c_i 很大，卻把 Phi 拉低得夠多，使差值 Phi(D_i) - Phi(D_{i-1}) 非常負，從而吸收了那個尖峰。
注意這份分工。規則 1 與 2 只關乎位勢函數本身，保證攤還成本是真實成本的合法上界。規則 3 才是分析真正見效的逐操作功夫。若三者都成立、且每個 a_i 至多為某個界 A，那麼整串 n 個操作的真實時間至多是 n 乘以 A，於是你便證出了每操作 A 的攤還界。
兩個案例，各用一個數字
拿你在聚合法那篇遇過的二進位計數器來看：一個你不斷遞增的位元陣列，每次遞增把一連串尾端的 1 翻成 0、再把一個 0 設成 1。自然的位勢是 Phi = 計數器中目前 1 位元的數目。它從 0 起步（全為零）、且永不為負——兩條誠實規則都過關。現在做一次遞增，把 k 個尾端的 1 翻成 0、把一個 0 變成 1。真實成本是 k + 1 次位元寫入。位勢下降 k（那些 1 變成 0）、上升 1（新的那個 1），淨變化為 1 - k。於是攤還成本是 (k + 1) + (1 - k) = 2。每一次遞增，不論進位鏈多長，攤還成本都恰好是 2——乾淨的 O(1)——而那個翻動一百個位元的巨大進位，全由當初把這些位元設為 1 的一百次存款買單。
再看表格倍增，那個滿了就把容量加倍的可增長陣列。多數插入是 O(1)，但讓陣列溢位的那一次，必須把現有的全部 n 個項目複製進一個兩倍大的新陣列——一個 O(n) 的尖峰。一個行得通的位勢是 Phi = 2 *（項目數）-（容量）。剛倍增完，表格半滿，所以 2 *(n/2) - n = 0；下次倍增之前，表格全滿，所以 Phi 已爬到 2n - n = n，恰好是複製 n 個項目所需的存款。每一次便宜的插入加入一個項目、把 Phi 推高 2，存下它自己日後搬遷的成本、外加一個較舊項目搬遷的成本。當那次昂貴的複製終於觸發時，它 O(n) 的真實成本，幾乎正好被一個 O(n) 的位勢跌幅抵銷，攤還成本便落在一個常數上。完整的數字是這一階最後一篇指南的主題；這裡的教訓只是：一個精選的數字如何馴服整串序列。
它給你什麼，又不給你什麼
位勢法是進階攤還分析的主力，正因為那個伸縮和是機械式的：一旦你定下一個 Phi，界要嘛攤開、要嘛攤不開，無須再用手追蹤散落的存款。它能擴展到那些用記帳法會淹沒在帳務裡的結構——它是分析 伸展樹、費氏堆積、以及你下一篇會遇到的並查集那個深刻的近常數界的標準工具。同一個伸縮論證也撐起了較早的聚合法，後者其實是「直接界定整個總和、而非一次一個操作」的特例。
對兩個限制要誠實。第一，這套方法完全不告訴你如何找到 Phi——選擇位勢函數是一樁真正的洞見之舉，一個選得差的 Phi 會給出一個雖真卻無用的界，或乾脆違反規則 1 與 2。抵銷是自動的；巧思在於那個選擇。第二，也同樣重要：攤還 O(1) 的界，是關於整串序列總成本的保證，而不是對任何單一操作的承諾。那個觸及全部 n 個項目的表格倍增複製，在它執行的那一刻確實花了 Theta(n) 的時間——你那個正等著這一次插入的使用者，會感受到其中的每一微秒。
最後這一點，正是攤還分析與平均情況分析分道揚鑣之處，值得把它釘牢。攤還界是一個最壞情況的陳述：它對每一串操作都成立，不對隨機性或輸入分布作任何假設。相對地，平均情況分析是在某個輸入分布上取平均，可能被一個倒楣的輸入毀掉。所以攤還成本是更強、更值得信賴的保證——它只是保證一串操作上的平均值，而從不保證其中某一次操作的耗時。把這個區別保持鋒利，位勢法就會成為你手上最可靠的工具之一。