攤還分析

選擇位勢函數

位勢法在你有了位勢函數 Phi 後給你一條照章辦事的公式,但對 Phi 從何而來保持沉默。找一個好的 Phi 才是攤還分析真正的藝術。好的位勢是一個數,衡量結構目前儲存了多少「蓄勢待發的未來成本」——昂貴操作將至時偏高,剛清理完後偏低。

兩個指路標讓搜尋變得可行。第一,Phi 必須遵守邊界條件:它絕不能跌破起始值(最簡單是 Phi >= 0 且 Phi(空) = 0),否則疊縮總和就不再是上界。第二,也是設計上的啟發法:挑 Phi 使便宜操作只抬高它一點點,而昂貴操作把它降低大約等於自身的那份大成本。如此昂貴操作的實際成本大半被 Phi 的下降抵消,於是一切的攤還成本都變小。實務上,你看是什麼讓某操作昂貴——許多元素要複製、長進位鏈、一條深而不平衡的路徑——再讓 Phi 恰好去數那份待辦工作。對接近滿的動態陣列,一個可行的位勢是 Phi = 2*(項目數) - 容量,它在剛擴容後很小,隨陣列填滿而增長,所以恰好在下一次昂貴加倍將至時很大。

選位勢是由直覺引導的猜測與檢驗:提出一個 Phi,對每個操作算「攤還 = 實際 + (Phi_後 - Phi_前)」,看它們是否都變小且邊界條件成立。若某操作的攤還成本仍大,位勢就錯了,你修改它。誠實的現實:沒有演算法把 Phi 交給你;對伸展樹這類困難結構,正確的位勢(各子樹大小取對數之和)需要真正的洞察才發現得出。錯誤的選擇不會給錯答案,只給沒用的界——所以放心實驗。

加倍的動態陣列,取 Phi = 2*大小 - 容量。一次不擴容的附加使大小加 1,故 Phi 升 2;攤還 = 1(寫入)+ 2 = 3。當容量 c 的滿陣列加倍時,複製花 c,但 Phi 從 2c - c = c 降到(重新填入前)2c - 2c = 0——這 c 單位的下降抵消了 c 單位的複製,使那次附加的攤還成本同樣是 O(1)。

讓位勢去數待辦的昂貴工作;便宜操作添一點,昂貴操作釋放一大批。

沒有食譜能替你生出 Phi。壞的位勢絕不會給出錯誤的界,只給鬆或沒用的界,所以猜測是安全的——但困難結構的正確 Phi 可能需要真本事。

又称
designing a potentialpicking Phi設計位勢挑選位勢