均摊分析

**平攤分析**在電腦科學中，是用於演算法分析中的方法，平攤分析常用於分析資料結構（動態的資料結構），在使用平攤分析前須知道資料結構各種操作所可能發生的時間，並計算出最壞情況下的操作情況並加以平均，得到操作的平均耗費時間。平攤分析只能確保最壞情況效能的每次操作耗費的平均時間，並不能確認平均情況效能。

一個簡單的例子，一個長度為 n 的 list，在 list 的最後要加入一筆新的資料此時要花費的操作時間為 O (n)，此時也是加入新的資料的最糟糕的情況。但是，一個 _n_ 個插入的操作序列仍然可以在 O (_n_) 的時間內完成，因為剩下的插入可以在常數時間內完成，因此 _n_ 個插入可以在 O (_n_) 的時間內完成。因此每操作的平攤耗費為 O (_n_) / _n_ = O(1)。

注意平攤分析與平均時間分析和概率演算法的概率分析不同。在平均時間分析中，我們平均化所有可能的輸入；在概率演算法的概率分析中，我們平均化所有可能的隨機選擇；在平攤分析中，我們平均化一系列操作的耗費。平攤分析假設的是最壞情況輸入並且通常不執行隨機選擇。

平攤分析中幾種常用的技術:

* 聚合分析決定 _n_ 個操作序列的耗費上界 _T_(_n_)，然後計算平均耗費為 _T_(_n_) / _n_。
* 記帳方法確定每個操作的耗費，結合它的直接執行時間及它在對執行時中未來操作的影響。通常來說，許多短操作增量累加成「債」，而通過減少長操作的次數來「償還」。
* 勢能方法類似記帳方法，但通過預先儲蓄「勢能」而在需要的時候釋放。

## 平攤分析種類

### 聚集法 (Aggregate method)

計算 n 個操作的時間複雜度上限 T (n)
平攤 T (n) 至每一個操作，每一個操作的平攤成本是 T (n)/n

### 記帳法 (Accounting method)

執行花費較低的 operations 時先存 credit 未雨綢繆，供未來花費較高的 operations 使用

對每個操作定義一個合法的平攤成本 (amortized cost)
假設 $c_{i}$ 為第 i 個操作的 actual cost， ${\hat {c_{i}}}$ 為第 i 個操作的 amortized cost

若 $c_{i}<{\hat {c_{i}}}$ ，則 credit= ${\hat {c_{i}}}-c_{i}$ ，我們把 credit 存起來 (deposited)，未來可以提取 (withdraw)
若 $c_{i}>{\hat {c_{i}}}$ ，則提取 credit

設定每個操作的平攤成本 (amortized cost) 後，要做 valid check 確保 credit 不可以是 0，也就是說 $\sum _{k=1}^{n}{\hat {c_{i}}}\geq \sum _{k=1}^{n}c_{i}$

### 位能法 (Potential method)

定義一個位能函式 (potential function) $\Phi (D)$ ，將資料結構 D (例如：堆疊) 的狀態對應到一個實數

　
: $D_{0}$ : 資料結構 D 的初始狀態

　
: $D_{i}$ : 資料結構 D 經過 $i$ 個操作後的狀態

　
: $c_{i}$ : 第 $i$ 個操作的 actual cost

　
: ${\hat {c_{i}}}$ : 第 $i$ 個操作的 amortized cost

定義 ${\hat {c_{i}}}=c_{i}+\Phi (D_{i})-\Phi (D_{i-1})$

$$
\sum _{k=1}^{n}{\hat {c_{i}}}=\sum _{k=1}^{n}(c_{i}+\Phi (D_{i})-\Phi (D_{i-1}))=(\sum _{k=1}^{n}c_{i})+\Phi (D_{n})-\Phi (D_{0})
$$

為了滿足 $\sum _{k=1}^{n}{\hat {c_{i}}}\geq \sum _{k=1}^{n}c_{i}$

我們定義 $\Phi (D_{n})-\Phi (D_{0})\geq 0$ , 通常令 $\Phi (D_{0})=0$ 和 $\Phi (D_{n})\geq 0$

## 例子

### 堆疊 (stack) 的平攤分析

我們定義一個堆疊有下列操作

S.mult-pop (k) 的程式碼如下

接下來我們分別使用聚集法 (aggregate method), 記帳法 (Accounting method), 位能法 (Potential method) 求出 "堆疊一個操作的平攤成本是 O (1)"

#### 使用聚集法 (aggregate method) 分析堆疊操作的平攤成本

令 $n_{push}$ 是 S.push (x) 的執行次數， $n_{pop}$ 是 S.pop () 的執行次數， $n_{multi-pop}$ 是 S.multi-pop (k) 的執行次數

　
: $n=n_{push}+n_{pop}+n_{multi-pop}$ 為總執行次數

因為一個堆疊 S 如果是空的，就不能執行 pop 了，也就是說可以 pop 或 multi-pop 的元素個數不會超過 S 中 push 進去的元素個數

所以 $n_{pop}+n_{multi-pop}\leq n_{push}$

假設 $T(n)$ 是執行 $n$ 個操作的時間複雜度上限

　
: $T(n)=O(1)\times n_{push}+O(1)\times n_{push}=O(n)$

所以堆疊一個操作的平攤成本為 $O(n)/n=O(1)$

#### 使用記帳法 (Accouting method) 分析堆疊操作的平攤成本

我們假設 S.push (x), S.pop (), S.multi-pop (k) 的 amortized cost 分別為 2, 0, 0，如下表所示

因此每個操作的平攤成本是 O (1)

 

#### 使用位能法 (potential method) 分析堆疊操作的平攤成本

我們定義位能函式 $\Phi (D)$ 為執行 i 個操作後，堆疊內的元素個數

　
: $\Phi (D_{0})=0$ ，因為堆疊一開始是空的

　
: $\Phi (D_{i})\geq 0$ ，因為堆疊的元素個數一定 $\geq 0$

計算堆疊 S 每一個操作的平攤成本

總平攤成本 $\sum _{k=1}^{n}{\hat {c_{i}}}=2\times n_{push}=O(n)$ ，所以堆疊單一個操作的平攤成本是 $O(n)/n=O(1)$

### 動態陣列

考慮一個隨元素個數增加而增長的動態陣列，比如 Java 的 ArrayList 或者 C++ 的 std::vector。如果我們的陣列大小從 4 開始，那麼來向其中增加四個元素的時間就是一個常數。然而，若要將第五個元素加入其中，那麼會花費更多時間，因為我們此時必須要建立一個兩倍於當前陣列大小的陣列（8 個元素），把老元素拷貝到新陣列中，然後增加一個新元素。接下來的三次加入操作也同樣會花費常數時間，然後在陣列被填滿後則又需要一輪新的加倍擴充。

一般地，如果我們考慮任意一個任意的 _n_ 大小的陣列並對其進行 _n_ + 1 次加入操作。我們注意到，所有的加入操作都是常數時間的，除了最後一個，它會花費 $O(n)$ 時間在大小加倍上。因為我們進行了 _n_ + 1 次加入操作，我們可以將陣列加倍的時間平攤到所有的加入操作上，因此得到加入操作的平均時間是 ${\tfrac {nO(1)+O(n)}{n+1}}=O(1)$ 。它是一個常數。

### 佇列

使用 Ruby 實現的佇列，一個先進先出資料結構:

佇列操作及特性參考佇列條目，enqeue 及 deqeue 操作時間複雜度為常數，
否則，dequeue 需要 $O(n)$ 時間將所有元素從輸入數組添加到輸出數組中，其中 _n_ 是輸入數組的當前長度。 從輸入複製 _n_ 元素後，我們可以在輸出數組再次為空之前執行 _n_ 出隊操作，每次操作都需要一個恆定的時間。 因此，我們可以僅在 $o(n)$ 時間執行一系列 _n_ 出列操作，這意味著每個出列操作的攤銷時間是 $O(1)$ 。

或者，我們可以收取將任何項目從輸入數組複製到輸出數組的成本，以及該項目的早期排隊操作。 該計費方案將入隊的攤還時間加倍，但將出列的攤還時間減少到 $O(1)$ 。

## 通常用法

* 在常見場合，我們把能很好平攤分析的演算法稱為「平攤演算法」。
* 線上演算法通常使用平攤分析。

## 參考資料