位勢法(potential method)
想像資料結構帶有某種儲存的能量,當結構變得「凌亂」時上升(陣列滿了、許多 1 位、樹不平衡),當某操作整理它時下降。便宜操作傾向添一點凌亂、存下能量;昂貴操作通常釋放大量儲存的能量來支付其工作。位勢法把這幅圖像化成單一函數與一條精確公式。
你挑一個位勢函數 Phi,把結構的任意狀態映到一個數,且 Phi 從不低於它的起始值(通常 Phi >= 0 且 Phi(初始) = 0)。一個操作的攤還成本於是「被定義」為它的實際成本加上它造成的位勢變化:攤還 = 實際 + (Phi_後 - Phi_前)。現在對整條序列求和:位勢變化會疊縮(telescope),所以攤還總成本等於實際總成本加上 Phi_末減 Phi_初。既然 Phi_末 >= Phi_初,攤還總成本至少等於實際總成本——於是把攤還成本加總給出對真實工作的有效上界。要界定單一操作,你只要算「實際 + 位勢變化」;若便宜操作抬高 Phi,它的攤還成本略多於實際;若昂貴操作大幅降低 Phi,這下降抵消了它大部分的實際成本。
位勢法是三種技巧中最機械化、最可重用的:一旦你有了好的 Phi,每個操作的攤還成本就是一道簡短計算,而疊縮自動保證了界。它是伸展樹、斐波那契堆、動態陣列的標準工具。它的難處完全在前頭——找一個讓每個操作的攤還成本都小的位勢。誠實的提醒:這方法從不告訴你 Phi 該是什麼;選位勢才是那個有創意、有時很難的部分。
二進位計數器,令 Phi = 1 位的個數。一次加一把 t 個 1 翻成 0 並把一個 0 設成 1,實際成本 t+1,使 Phi 變化 (1 - t)。攤還 = (t+1) + (1 - t) = 2,與進位鏈多長無關。昂貴的連鎖正是那些大幅降低 Phi 的操作,抵消了它們的成本。
攤還成本 = 實際成本 + 位勢變化;對序列求和時這些變化疊縮,給出有效的總界。
疊縮之所以給出上界,全靠 Phi_末 >= Phi_初。若你讓 Phi 在序列中途跌破起始值,界可能崩——要讓 Phi 全程維持在初始值或以上。