攤還分析

聚合法(aggregate method)

找攤還成本最直接的方法也最樸素:把整條序列的實際成本加起來,再除以操作數。沒有巧妙的記帳,也沒有逐操作的收費——你直接界定總和,再均分。這就是聚合法,只要你能把序列當作一個整體來推理而非一次一個操作,它就管用。

做法分兩步。第一,對從空狀態開始的「任意」m 個操作序列,證明一個總成本上界 T(m)。第二,宣告每個操作的攤還成本為 T(m)/m。因為對每種操作都指派同一個數 T(m)/m,這方法給出單一且一致的攤還成本。以二進位計數器為例,把 n 位計數器從 0 加到 m 次,每次都翻第 0 位(m 次翻轉),每隔一次翻第 1 位(約 m/2 次),每隔四次翻第 2 位,依此類推;總翻轉數至多 m(1 + 1/2 + 1/4 + ...) < 2m。所以 T(m) < 2m,每次加一的攤還成本是 2m/m = 2 = O(1),即使一次加一可能翻動全部 n 位。

聚合法的魅力在於它不需要洞察哪些操作昂貴——你只要界定整筆帳。它的限制正是這份樸素:它對每個操作指派「相同」的攤還成本,當不同操作該收不同的費時(便宜的查詢對上昂貴的插入)這可能浪費。當你想對操作差別收費時,記帳法或位勢法更靈活。但當一個全域總和容易算出時,聚合分析是得到誠實攤還界最快的路。

對加倍動態陣列做 n 次附加:簡單寫入總共花 n;擴容時的複製花 1 + 2 + 4 + ... + n/2 < n。總計 T(n) < 2n,所以每次附加的攤還成本是 T(n)/n < 2 = O(1)。一個總和就一次界定了整條序列。

界定整條序列的總成本,再除以操作數——同樣的成本攤給所有操作。

聚合法對每個操作指派一個相同的攤還成本。若你的結構有好幾種真的該收不同費用的操作,記帳法或位勢法通常更合適。

又称
aggregate analysis聚合分析總和法