研究所考試

在《分攤分析(2)》中，我們介紹了分攤分析中第三種常見的方法：勢能法，透過定義勢能函數來將不同操作的成本透過勢能來分攤，當第 i 次操作的勢能差 Φ(D_i) - Φ(D_i-1) 為正，則攤銷代價 ĉ_i 代表對第 i 次操作的多收費；若勢能差為負，則攤銷代價代表對第 i 次操作的少收費，而勢能的減少支付了該操作的實際代價。在本文中，我們要用另一個常見的範例：二進位計數器遞增，來演示如何透過聚合分析、會計法以及勢能法來解決此問題。

我們來考慮實現一個從 0 開始向上計數的 k 位元（k-bit）二進位計數器的問題。我們用一個位元陣列 A[0...k-1] 來表示這個計數器。儲存在計數器中的二進位數 x，其最低有效位元位於 A[0]，最高有效位元位於 A[k-1]，因此可得以下等式：

初始時 x = 0，因此對於 i = 0, 1, … , k-1，皆有 A[i] = 0。若要將計數器中的值加 1，可以呼叫以下 INCREMENT 程序：

下圖顯示了當 INCREMENT 被呼叫 16 次時，二進位計數器所發生的變化，其初始值為 0，最終值為 16。第 2-4 行中 while 迴圈的每次疊代，都會將位元位置 i 加上1。如果 A[i] == 1，那麼加上 1 就會將位置 i 的位元翻轉為 0，並產生一個進位值 1，這個進位將在迴圈的下一次疊代中被加到位置 i+1 中。否則，迴圈結束。此時如果 i < k，則 A[i] 必然為 0，因此第 6 行會將 1 加到位置 i，將 0 翻轉為 1。如果迴圈結束時 i = k，那麼這次 INCREMENT 的呼叫會將所有 k 個位元從 1 翻轉為 0。

每次 INCREMENT 操作的成本，與被翻轉的位元數量呈線性關係。當進位的程度越多，需要翻轉的成本就越高，例如當1變成2時，二進位計數器會先將A[0]由1翻轉為0，再將A[1]由0翻轉為1，成本為2；當3變成4時，二進位計數器會先將A[0]由1翻轉為0，將A[1]由1翻轉為0，最後再將A[2]由0翻轉為1，成本為3。

與堆疊（Stack）的例子類似，粗略的分析會得到一個正確但不緊確（not tight）的上限。在最壞情況下，單次執行 INCREMENT 需要 θ(k) 的時間，此時陣列 A 中的所有位元皆為 1。因此，在一個初始為零的計數器上執行一系列 n 次 INCREMENT 操作，在最壞情況下需要 O(nk) 的時間。

雖然單次呼叫 INCREMENT 可能會翻轉所有 k 個位元，但並非每次呼叫都會翻轉所有位元。（與 MULTIPOP 的相似之處：單次呼叫可能會彈出許多物件，但並非每次呼叫都會彈出很多物件。）正如上圖所示，每次呼叫 INCREMENT 時，A[0] 都會翻轉。而往上一位的 A[1]，則是每兩次呼叫才翻轉一次。因此，在一個初始為零的計數器上執行一系列 n 次 INCREMENT 操作，會導致 A[1] 翻轉 n/2 次。同理，位元 A[2] 每四次呼叫才翻轉一次，在 n 次 INCREMENT 操作中翻轉 n/4 次。一般來說，對於 i = 0, 1,..., k-1，位元 A[i] 在初始為零的計數器進行 n 次 INCREMENT 操作的序列中，會翻轉 n/2ⁱ 次。因此，總翻轉次數爲：

因此，在一個初始為零的計數器上執行一系列 n 次 INCREMENT 操作，在最壞情況下需要 O(n) 的時間。每次操作的平均成本，同時也是每項操作的分攤成本為 O(n)/n = O(1)。

為了進行平攤分析，我們將「把一個值為 0 的位元設置為 1」的平攤成本訂為 $2。當一個位元被設置為 1 時，這 $2 當中的 $1 會用來支付實際設置該位元的成本；而第二個 $1 則會作為「信用（Credit）」留存在該位元上，以便日後該位元被重新設置（reset）回 0 時使用。在任何時間點，計數器中的每一個「1 位元（1-bit）」上都存有 $1 的信用，因此，將一個位元重新設置回 0 可以被視為「不花費任何成本」，因為該位元上的 $1 已經預先支付了這次重設的費用。

以下是確定 INCREMENT 平攤成本的方法：在 while 迴圈中將位元重新設置為 0 的成本，是由那些被重設的位元上所存有的美元（信用）來支付的。而 INCREMENT 程序在第 6 行中，最多只會將一個位元設置為 1，因此一次 INCREMENT 操作的平攤成本最多為 $2。計數器中「1 位元」的數量永遠不會變成負數，因此信用的總額在所有時間也都保持為非負值。因此，對於 n 次 INCREMENT 操作，總平攤成本為 O(n)。

這一次，我們將計數器在執行第 i 次 INCREMENT 操作後的位能（potential），定義為該操作後計數器中「1 位元」的數量，我們將其記為 b_i。以下是如何計算一次 INCREMENT 操作的平攤成本。假設第 i 次 INCREMENT 操作將 t_i 個位元重新設置為 0。因此，該操作的實際成本 c_i 最多為 t_i+1 ，因為除了將 t_i 個位元重設為 0 之外，它最多還會將一個位元設置為 1。如果 b_i = 0 ，代表第 i 次操作已將所有 k 個位元都重設為 0，因此 b_i-1 = t_i = k。如果 b_i>0，則有 b_i = b_i-1-t_i+1。不論哪種情況，皆滿足 b_i≤b_i-1-t_i+1，此時的位能差為：

如果計數器從 0 開始，那麼 Φ(D₀) = 0。由於對所有 i 而言皆有 Φ(D₀) ≥ 0，因此一系列 n 次 INCREMENT 操作的總平攤成本，即為總實際成本的一個上限，所以 n 次 INCREMENT 操作在最壞情況下的成本為 O(n)。

假設計數器一開始有 b₀ 個「1 位元」，在執行 n 次 INCREMENT 操作後，它擁有 b_n 個「1 位元」，其中 0≤b₀, b_n≤k。我們可以將公式改寫為：

因為 Φ(D₀) = b₀、Φ(D_n) = b_n，且對於所有 1≤i≤n，皆滿足 ĉ_i≤2，所以 n 次 INCREMENT 操作的總實際成本為：

由於 b₀≤k，這意味著只要 k = O(n)，總實際成本就是 O(n)。換句話說，如果至少進行了 n = Ω(k) 次 INCREMENT 操作，那麼無論計數器的初始值為何，其總實際成本都會是 O(n)。

我們透過二進位計數器遞增這個例子，重新把分攤分析當中的三個方法：聚合分析、會計法以及勢能法再進行一次實作分析。相信各位同學經過之前堆疊問題以及本次二進位計數器遞增的練習，已經很熟悉分攤分析的方法了。在未來，我們的專欄會提到線上演算法，其特色為並不會在最一開始就有完整輸入，而是會隨時間逐步接收輸入。在解決線上演算法的多種方法中，會利用到分攤分析的概念來解決，希望能協助各為同學順利上手。