研究所考試
在演算法設計與分析中，時間複雜度通常以最好情況（best-case）、最壞情況（worst-case）或平均情況（average-case）作為評估標準。然而，某些資料結構的操作雖然在個別步驟上可能代價高昂，但在一連串操作的整體過程中，其平均成本卻相對低廉。因此分攤分析（amortized analysis）的概念被提出，它並非計算機率意義下的期望時間，而是在不依賴任何隨機假設的前提下，對最壞情況序列中的每一次操作分攤成本，從而得到每個操作的分攤時間界限。換句話說，即使單次操作可能需要較高的時間代價，只要整體操作序列的總成本受到良好控制，我們仍可證明其分攤成本為常數或其他可接受的時間界限。
在接下來的一系列專欄裡，我們會逐步介紹分攤分析中幾種常見的分攤方式，包含聚合分析（aggregate analysis）、會計法（the accounting method）與勢能法（the potential method）等方法，並以實際的資料結構及其操作為例子，去分析其效能。本次文章，我們會先聚焦在介紹分攤分析（amortized analysis）在CLRS中的定義，並介紹如何透過聚合法與會計法在堆疊問題上分攤成本。
在這個時代提到運動，很多人會直覺想到跑健身房，無論是有氧或是重訓都可以在健身房裡完成。假設你加入了某家健身房，每個月收取 60 美元的會員費，外加每次使用健身房 3 美元的費用。你是一個非常自律的人，在這個月裡你每天都去健身房，因此除了固定會費60 美元以外，你還需要支付90美元的使用費（假設這個月有30天）。你可以將這筆費用視為 60 美元的固定費用和另外 90 美元的每日費用，但你也可以換個方式思考。你可以說整體而言，你在這30天內總共付了150美元；你也可以說在這30天裡，你每天付了5美元。當你以這種方式看待費用時，你正在將月費攤銷（amortizing）到該月的 30 天中，以每天 2 美元的形式分攤出去。
你在分析執行時間時也可以做同樣的事情。在分攤分析（amortized analysis）中，你會對資料結構執行的一系列操作所需的時間，在所有執行的操作上取平均值。透過分攤分析，你可以證明如果對一系列操作取平均，則操作的平均成本很小，即使該序列中的單個操作可能非常昂貴。分攤分析與平均情況分析（average-case analysis）不同，因為它不涉及機率。分攤分析保證了在最壞情況下每個操作的平均效能。
我們先來簡單介紹本次的兩種分析方法。在聚合分析（aggregate analysis）中，你會確定一個由 n 個操作組成的序列之總成本 T(n) 的上界。每個操作的平均成本即為 T(n)/n。你將此平均成本視為每個操作的分攤成本，因此所有操作都具有相同的分攤成本。在會計法（the accounting method）中，你會確定每個操作的分攤成本。當存在多種操作類型時，每種操作類型可能具有不一樣的分攤成本。會計法會對序列早期的某些操作過度收費，並將過度收費的部分作為「預付信用額度」存儲在資料結構中的特定對象上。隨後在序列中，這些信用額度會支付給那些收費低於其實際成本的操作。話不多說，就讓我們來看看這兩個方法是如何分析堆疊問題的操作成本。
在聚合分析中，你需要證明對於所有的 n，一個由 n 個操作組成的序列在最壞情況下總共耗時 T(n)。因此在最壞情況下，每個操作的平均成本或稱分攤成本為 T(n)/n。即使序列中有多種類型的操作，此分攤成本也適用於每個操作。
定義堆疊問題 讓我們先來介紹堆疊問題。有兩項大家都很熟悉的堆疊操作，耗時皆為O(1)。- PUSH(S,x)：將物品 x 推入堆疊 S。
- POP(S)：從堆疊 S 的頂部彈出一個對象並返回該對象。在空堆疊上呼叫 POP 會產生錯誤。
現在讓我們增加堆疊操作 MULTIPOP(S, k)，它會移除堆疊 S 頂部的 k 個對象，如果堆疊中包含的對象少於 k 個，則彈出整個堆疊。當然，該程序假設 k 是正數，否則 MULTIPOP 操作不會改變堆疊。在 MULTIPOP 的虛擬碼中，操作 STACK-EMPTY 如果堆疊上目前沒有對象則返回 TRUE，否則返回 FALSE。
讓我們來看一個實際例子。假設有一堆疊如(a)所示，而我們對其執行MULTIPOP(S, 4)。此時堆疊頂部的四個物品會被彈出來，讓堆疊變成(b)的樣子。隨後，我們對其執行MULTIPOP(S, 7)，此時因為堆疊內的物品總數少於7，因此這個操作會直接清空堆疊。
那麼，MULTIPOP(S, k) 在包含 s 個對象的堆疊上的執行時間是多少？ 實際執行時間與實際執行的 POP 操作次數成線性關係，因此我們可以根據 PUSH 和 POP 各自為 1 的抽象成本（abstract costs）來分析 MULTIPOP。while 迴圈的迭代次數是從堆疊中彈出的對象數量 min{s, k}。迴圈的每次迭代都會在第 2 行調用一次 POP。因此，MULTIPOP 的總成本是 min{s, k}，也就是成本為1的POP被執行的總次數，而實際執行時間是此成本的線性函數。
堆疊操作的聚合分析現在讓我們分析在一個初始為空的堆疊上執行由 n 個 PUSH、POP 和 MULTIPOP 操作組成的序列。序列中一個 MULTIPOP 操作的最壞情況成本是 O(n)，因為堆疊大小最多為 n。任何堆疊操作的最壞情況時間因此是 O(n)，因此 n 個操作的序列成本為 O(n2)，因為序列包含最多 n 個每個成本為 O(n) 的 MULTIPOP 操作。
儘管這種分析是正確的，但考慮單個操作的最壞情況成本而得到的 O(n2) 結果並不嚴謹。 不可否認單個 MULTIPOP 操作的成本可能很昂貴，但聚合分析顯示，在初始為空的堆疊上，任何由 n 個 PUSH、POP 和 MULTIPOP 操作組成的序列，其成本上界為 O(n)。為什麼可以這樣分析？關鍵因素是，一個物品除非先被推入（pushed），否則無法從堆疊中彈出（popped）。我們可以進一步推論，可以執行 POP 的次數（包括 MULTIPOP 內部的執行）最多等於 PUSH 操作的次數，而後者最多為 n。因此，對於任何 n 值，任何 n 個 PUSH、POP 和 MULTIPOP 操作的序列總共花費 O(n) 時間。在 n 個操作上取平均，得到每個操作的平均成本為 O(n)/n = O(1)。聚合分析將每個操作的分攤成本指定為平均成本。因此在該範例中，所有三個堆疊操作的分攤成本皆為 O(1)。
在會計法中，你會對不同的操作賦予不同的費用，有些操作收取的費用比其實際成本更多或更少。你對一個操作收取的金額被稱為其平攤成本（amortized cost）。當一個操作的平攤成本超過其實際成本時，你會將差額分配給資料結構中的特定對象，作為信用（credit）。信用可以幫助支付後續那些平攤成本低於實際成本的操作。因此，你可以將一個操作的平攤成本看作是分成了兩個部分：實際成本以及存入或消耗掉的信用。不同的操作可能有不同的平攤成本。這種方法與聚合分析不同，在聚合分析中，所有操作都具有相同的平攤成本。
堆疊操作的會計法 我們回到堆疊的例子。回想一下，三個操作的實際成本為：- PUSH：1
- POP：1
- MULTIPOP： min{s, k}
- PUSH：2
- POP：0
- MULTIPOP： 0
看起來很不可思議對吧？怎麼會有操作的成本直接變成0了？別急，現在就讓我們看看如何透過收取平攤成本來支付任何堆疊操作序列。令 $1 代表一個單位的成本。起初，堆疊是空的。此時我們把堆疊資料結構比喻成自助餐廳中一疊盤子。當把一個盤子推入（PUSH）堆疊時，使用 $1 來支付推入的實際成本，留下 $1 的信用（從收取的 $2 中扣除）。將這 $1 信用放在盤子上方。在任何時間點，堆疊中的每個盤子上都有 $1 的信用。
存放在盤子上的 $1 用於預付將該盤子從堆疊中彈出的成本。POP 操作不收取費用：透過從盤子取走 $1 信用，來支付彈出盤子的實際成本。因此，藉由對 PUSH 操作多收一點點費用，我們可以將 POP 操作視為免費。換句話說，執行POP的成本在執行PUSH的時候就先收起來，這樣在執行POP時就不用再收一次錢啦！
同樣的，MULTIPOP 操作也不收取費用，因為它只是重複的 POP 操作，而其中的每一次 POP 都是免費的。如果一個 MULTIPOP 操作彈出了 k 個盤子，則實際成本是由儲存在這 k 個盤子上的 $k 支付的。因為堆疊中的每個盤子都有 $1 信用，且堆疊的盤子數量始終為非負數，所以信用的總量始終是非負的。因此，對於任何包含 n 個 PUSH、POP 和 MULTIPOP 操作的序列，總平攤成本是總實際成本的一個上界。由於總平攤成本是 O(n)，因此總實際成本也是 O(n)。
透過本次文章，我們介紹了分攤分析，其特色為均攤 n 項操作裡不同操作的時間成本，以平均不同操作之間的時間成本。首先我們介紹聚合分析（aggregate analysis），先計算出所有操作的總時間成本，再將整體的時間成本均攤到 n 次操作中。接著我們介紹會計法（the accounting method），透過平攤成本（amortized cost），將不同操作的成本透過信用去調整，使成本集中於容易被估算的操作上，使整體成本更容易去計算。希望透過本次內容，讓各位讀者對於分攤分析的原理以及兩大方法有所認識。