並查集與伸展樹各自證明了「單次可以很慢，一串操作仍然很快」。那兩篇把位能算在特定結構上。本篇把三種通用算法寫清楚：聚集法、記帳法、位能法，並用二元計數器與動態陣列當可以手算的例子。之後再回去看並查集與伸展樹，會知道它們只是位能函數不同。

相關教材：Disjoint_Set_Teaching_Materials.md、Splay_Tree_Teaching_Materials.md、Heap_Priority_Queue_Teaching_Materials.md。

目錄

  1. 攤還不是平均
  2. 聚集法
  3. 記帳法
  4. 位能法
  5. 動態陣列
  6. 和均攤到各資料結構的關係
  7. 常見陷阱
  8. 練習題

1. 攤還不是平均

平均情況對輸入分布取期望。換一組輸入，期望可以不成立。

攤還是對任意輸入的一串操作給上界：(n) 次操作的總成本是 (T(n))，則每次攤還成本是 (T(n)/n)。其中幾次可以很貴，貴的次數被便宜的次數補上。沒有機率。

最壞單次成本仍然可能是 (O(n))。呼叫端若要求每一次都是 (O(1)) 最壞（即時系統），攤還 (O(1)) 不夠，要換一個真正最壞 (O(1)) 的結構。

2. 聚集法

直接把 (n) 次操作的總成本加總，再除以 (n)。

二元計數器。 從 0 開始做 (n) 次加一。成本定義成「這一次翻轉了幾個位元」。

次數 計數器 翻轉數
1 0001 1
2 0010 2
3 0011 1
4 0100 3
5 0101 1

第 (k) 個位元（從 0 數）每 (2^k) 次才翻轉一次，(n) 次操作裡大約翻 (n/2^k) 次。總翻轉數

[ \sum_{k=0}^{\lfloor\log n\rfloor} \frac{n}{2^k} < n\sum_{k=0}^{\infty}\frac{1}{2^k} = 2n ]

所以 (n) 次加一的總成本 (< 2n)，攤還每次 (O(1))。單次最壞仍是 (O(\log n))（從 (2^k-1) 進位到 (2^k)）。

聚集法的缺點是：操作種類一多，總成本不容易閉式求和。記帳法與位能法把「預存的便宜」放在結構上，方便一次只看一個操作。

3. 記帳法

每次操作付一個固定的攤還費用。實際成本較低時，多餘的錢存成結構上的信用。實際成本較高時，用存好的信用付。規則：信用永遠不能變成負的。那麼攤還費用的總和就是總成本的上界。

動態陣列 push。 容量滿了就把容量加倍，把舊元素複製過去。

收費：每次 push 收 3 元。

  • 1 元付這次寫入。
  • 1 元存在這個新元素上，留給它以後被複製。
  • 1 元存在陣列裡「較舊的那一半」某個還沒有信用的元素上。

容量從 (n) 倍增到 (2n) 時，要複製 (n) 個元素。這 (n) 個元素在上一次倍增之後的 (n) 次插入裡，已經各自被存了複製用的 1 元。信用夠付這次複製，不會變負。因此每次 push 的攤還成本是 3，(n) 次是 (O(n))。

縮容量要另外設計（例如降到 1/4 才縮回一半），否則在門檻附近來回 push/pop 會每次都重配，信用制度會破功。

4. 位能法

位能 (\Phi) 是結構狀態的函數，(\Phi \ge 0)，初始通常為 0。一次操作的攤還成本定義成

[ \hat{c} = c + \Delta\Phi = c + \Phi_{\text{after}} - \Phi_{\text{before}} ]

把一串操作加起來，中間的 (\Phi) 消掉，只剩總實際成本 (= \sum\hat{c} + \Phi_0 - \Phi_n)。若 (\Phi_n \ge 0=\Phi_0)，總實際成本 (\le \sum\hat{c})。

同一個動態陣列。 令 (n) 為元素個數、(c) 為容量，

[ \Phi = 2n - c ]

空陣列 (n=c=0)，(\Phi=0)。只要 (c \ge n) 且倍增策略讓 (c < 2n) 在插入後成立，(\Phi) 不會長期為負；倍增當下要單獨算。

不倍增的 push：實際成本 1，(n) 加 1，(\Delta\Phi=2)，攤還成本 (1+2=3)。

觸發倍增的 push：設當下 (n=c)（已滿）。複製成本 (c)，然後 (n) 變成 (c+1)、容量變成 (2c)。

  • 之前 (\Phi = 2c - c = c)
  • 之後 (\Phi = 2(c+1) - 2c = 2)
  • (\Delta\Phi = 2-c)
  • 實際成本 (c+1)
  • 攤還成本 ((c+1)+(2-c)=3)

兩種 push 的攤還都是 3。這和記帳法的 3 元是同一件事的兩種記法。

5. 動態陣列

把上面的結論收成可以使用的事實：

操作 最壞單次 攤還
push（倍增） (O(n)) (O(1))
依索引讀寫 (O(1)) (O(1))
pop（不縮容量） (O(1)) (O(1))

(n) 次從空陣列 push 的總複製成本是 (1+2+4+\cdots+n < 2n)，聚集法直接得到同一個 (O(n))。三種方法應該得出同一階，若差了一階，是位能或收費設錯，不是資料結構突然變了。

std::vector 的成長就是這個策略。迴圈裡 push_back (n) 次是線性，不是每次 (O(n)) 的二次。若事先知道長度，reserve 把那一次配置提前付清，連攤還都不需要。

6. 和均攤到各資料結構的關係

結構 貴的那一次 位能在量什麼 攤還結果
動態陣列 倍增複製 元素數相對容量的「滿度」 push (O(1))
二元計數器 連續進位 也可以用「1 的個數」當位能 加一 (O(1))
並查集 沿長路徑找根 見並查集教材；和秩、路徑壓縮綁在一起 近乎 (O(1))
伸展樹 一次 splay 沿路旋轉 節點深度的對數位能 搜尋 (O(\log n))

不要把伸展樹的攤還 (O(\log n)) 說成最壞 (O(\log n))。單次 splay 可以碰到 (\Theta(n)) 的鏈。

堆積的插入是最壞 (O(\log n))，不是攤還。不要為了用本篇的詞彙，把最壞界講成攤還界。

7. 常見陷阱

  • 用期望代替攤還。 快速排序的 (O(n\log n)) 是平均，洗牌沒做就沒有。動態陣列的線性總成本不需要隨機。
  • 位能最後是負的。 總和式不再是上界。設計完要檢查 (\Phi\ge 0)。
  • 只分析 push、產品同時在門檻上 pop。 縮容量的策略要一起寫進位能，否則攤還會被打壞。
  • 把攤還界寫進程式的延遲保證。 使用者若在倍增那一次被卡住，攤還救不了那一幀。
  • 聚集法的總和漏掉某一種操作。 (n) 次 push 加上 (n) 次依索引寫入，後者每次 (O(1))，總和仍線性；若中間夾了會掃全表的操作，要另外加。

8. 練習題

  1. 計數器從 0 加到 16（做 16 次加一）。最低位元翻幾次？次低位元呢？總翻轉數的上界 (2\times 16=32)，實際比 32 小還是可能超過？
  2. 動態陣列容量序列是 1,2,4,8。從空陣列 push 8 次，複製了幾個元素？
  3. 用 (\Phi=2n-c)，說明不倍增的 push 攤還成本是 3。
  4. 為什麼「滿了才倍增、一空一格就縮回一半」會讓攤還失敗？
  5. 並查集教材的近乎常數，是平均情況還是攤還？差在哪一句話？

參考答案

  1. 最低位元每次都翻，16 次。次低位元每兩次翻一次，8 次。總翻轉數小於 32，因為 (\sum n/2^k) 的上界是把無窮等比加滿才到 (2n)，實際位元數有限，而且最後一次不會把所有理論上的高位都用完。不會超過這個上界。
  2. 容量 1→2 複製 1 個，2→4 複製 2 個，4→8 複製 4 個，共 7 個。第 8 次寫入本身不再複製。
  3. 實際成本 1，(n) 增加 1、(c) 不變，(\Delta\Phi=2)，(1+2=3)。
  4. 容量 (n) 已滿時 push 倍增到 (2n)，接著 pop 一個就縮回 (n)，再 push 又倍增。每次都複製 (\Theta(n)) 個元素，信用還沒存夠就被花掉，(n) 次這樣的配對是 (\Theta(n^2))。延後到剩 1/4 才縮，才能讓縮容也有信用可付。
  5. 是攤還。對任意的 Union/Find 交錯序列，總成本是近乎線性，不需要假設哪一種操作比較常出現。平均情況則要一個輸入分布。

小結

攤還是一串操作的總成本除以次數，對任意輸入都成立。聚集法直接求和，記帳法把多收的錢存在物件上，位能法用一個非負函數把貴的操作前後的落差算出來。動態陣列三種算法都得到每次 push 攤還 (O(1))。並查集與伸展樹是同一個位能法，只是 (\Phi) 長在樹高上。