Algorithm - 平攤分析 Amortized Analysis

算法分析中，平攤分析尋找在最壞情況下的操作序列中每操作的平均耗費時間。這個方法需要知道操作序列中可能發生的每個操作。通常應用在操作間存在狀態的資料結構中。基本思想是，一個最壞情況操作會改變狀態而不會在一段時間內再次出現，因此「平攤」它的耗費。

例如：動態數組中，我們在每次數組溢出時增長數組的長度至原來的兩倍。因此需要數組空間分配，在最壞情況下一個插入操作需要O(n)的時間。但是，一個 n 個插入的操作序列仍然可以在 O(n) 的時間內完成，因為剩下的插入可以在常數時間內完成，因此 n 個插入可以在 O(n) 的時間內完成。因此每操作的平攤耗費為O(n) / n = O(1)。


[用心去感覺] 注意平攤分析、平均時間分析和機率分析不同
平攤分析完全不牽涉到機率，保證「最壞情況」性能的每操作耗費時間，且不涉及「平均情況」性能

• 在平均時間分析中，平均化所有可能的輸入
• 在機率分析中，平均化所有可能的隨機選擇
• 在平攤分析中，平均化一系列操作的耗費

平攤分析中常用的技術

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

CASE STUDY 1 : 堆疊操作 stack (首例附上各種方法的詳細解說)
假設我們要處理一個資料結構，一個堆疊要做一連串的PUSH、POP和MULTIPOP動作。為了彰顯問題所在，以下我們考慮會做三種操作子 :

• PUSH(S,x) : 將x壓入S
• POP(S) : 彈出堆疊頂
• MULTIPOP(S,k) : 彈出堆疊頂k個元素

0. 鬆散分析(隨便亂算)

• 一次PUSH(S,x) : O(1)
• 一次POP(S) : O(1)
• 一次MULTIPOP(S,k) : O(min(|S|,k))

每個操作的最壞情況時間是$O(n)$(multipop)，因此n個操作的序列的代價是$O(n^2)$，雖然這個分析正確，但界不夠緊。


1. 聚集分析(aggregate analysis)
利用聚集分析，可以獲得更好的上界。聚集分析使用硬功夫精準累計，但這個方法對複雜一點的問題有時不易施展。

由n個操作序列，其作用於一個初始為空的堆疊。一個元素在每次被壓入堆疊後，至多被彈出一次。所以，用POP (包括MULTIPOP)的次數至多等於PUSH的次數，即至多為n。

對任意的n，包含n個PUSH, POP, MULTIPOP操作的序列的總時間為O(n). 每個操作的平均代價為 O(n) / n = O(1)。 聚集分析中，將每個操作的平攤代價指派為平均代價。所以三個堆疊操作的平攤代價都是O(1)。


2. 記帳方法 (accounting method)
在平攤分析的記帳方法中，對不同的操作賦予不同的費用，某些操作的費用比它們的實際代價或多或少。

我們對一個操作的收費的數量稱為平攤代價。當一個操作的平攤代價超過了它的實際代價時，兩者的差值就被當作存款(credit)，並賦予資料結構中的一些特定元素，可以用來補償那些平攤代價低於其實際代價的操作。這種方法與聚集分析不同的是，對後者，所有操作都具有相同的平攤代價。

資料結構中存儲的總存款等於總的平攤代價和總的實際代價之差。注意：總存款不能是負的。

實際代價：

• PUSH : 1
• POP : 1
• MULTIPOP : min(k, s)

賦予以下的平攤代價(amortized cost)：

• PUSH : 2
• POP : 0
• MULTIPOP : 0

假設用1元錢來表示代價的單位。開始時堆疊為空。

當一個元素被壓入堆疊時，用2元中的1元付給「時間複雜度」(因為實際代價是1元)。剩下的1元就跟隨「元素」暫存在一起，稱作存款(credit)。當此元素被彈出來時，他就用存款去付時間複雜度(注意此時沒有拿出其他的錢來付帳，而是用存款)，同理，也無需對MULTIPOP收取任何費用。

因為堆疊上的每個元素上面都有1元，而且堆疊中總有非負個數的元素，就保證了存款的總量總是非負的。這樣，對任意的包含n次PUSH, POP, MULTIPOP操作的序列，總的平攤代價就是總的實際代價的一個上界。

以「會計師」的角度，最多做 n 次 push，每次 2 元
 $T(n) \leq 2n$ 因此 $T(n) = O(n)$, $T(n) / n = O(1)$


3. 勢能方法 (potential method)
勢能方法(potential  method)不是將已預付的工作作為存在資料結構特定元素中存款來表示，而是表示成「勢能」，它在需要時可以釋放出來，以支付後面的操作。勢能是與整個資料結構而不是其中的個別元素發生聯系。

對一個初始資料結構$D_0$執行 n 個操作。對每個 i，設$c_i$為每個操作的實際代價，

$D_i$ 為對資料結構 $D_{i-1}$ 執行第 i 個操作的結果。勢函數$\Phi$將每個資料結構 $D_i$ 映射為一個實數$\Phi(D_i)$，即與$D_i$相聯系的勢。第 i 個操作的平攤代價$a_i$根據勢函數$\Phi$定義為：

$a_i  = c_i + \Phi(D_i) - \Phi(D_{i-1})$

每個操作的平攤代價為其實際代價$c_i$加上由於該操作所增加的勢。而 n 個操作的總的平攤代價為 :

$\sum a_i ＝ \sum c_i ＋\Phi(D_n) - \Phi(D_0)$

如果我們能定義一個勢函數$\Phi$使得對所有n，有$\Phi(D_n) \geq \Phi(D_0)$, 則總的平攤代價$\sum a_i$就是總的實際代價$\sum c_i$的一個上界。通常為了方便起見定義 $\Phi(D_0) ＝ 0$。

直觀上看，如果第 i 個操作的勢差 $\Phi(D_i) - \Phi(D_{i-1})$是正的，則平攤代價 $a_i$ 表示對第 i 個操作多收了費，同時資料結構的勢也隨之增加了。如果勢差是負值，則平攤代價就表示對第 i 個操作的不足收費，這是通過減少勢來支付該操作的實際代價。

平攤代價依賴於所選擇的勢函數 $\Phi$。不同的勢函數可能會產生不同的平攤代價，但它們都是實際代價的上界。最佳勢函數的選擇取決於所需的時間界。

例如：堆疊操作中，定義堆疊上的勢函數$\Phi$為堆疊中元素的個數。開始時要處理的空堆疊$D_0$，且$\Phi(D_0)＝0$。因為堆疊中的元素數始終時非負的，故在第 i 個操作後，堆疊$D_i$就具有非負的勢。

以$\Phi$表示的 n 個操作的平攤代價的總和就表示了總的實際代價的一個上界。

現在計算各個操作的平攤代價。

• 如果作用於一個包含s個元素的堆疊上的第 i 個操作是PUSH，則勢差為：
  $\Phi(Di) － \Phi(D_{i-1}) = (s+1) – s = 1$
  
  而這個PUSH操作的平攤代價為：
  $a_i ＝   c_i  ＋ \Phi(D_i) － \Phi(D_{i-1}) = 1+1 = 2$
• 如果作用於一個包含s個元素的堆疊上的第 i 個操作是MULTIPOP(S, k)，則勢差為：
  $\Phi(D_i) － \Phi(D_{i-1}) = - min(s, k)$
  
  因此MULTIPOP操作的平攤代價為
  $a_i ＝   c_i  ＋ Φ(Di) － Φ(Di-1) ＝ min(s, k) - min(s, k) = 0$
• 同理，POP操作的平攤代價也是0。

三種堆疊操作的每一種的平攤代價都是$O(1)$， 這樣包含n個操作的序列的總平攤代價就是$O(n)$。已經證明 n 個操作的平攤代價的總和是總的實際代價的一個上界。所以n個操作的最壞情況代價為$O(n)$。




CASE STUDY 2 : Incrementing a binary counter
有一個 k-位元的二元計數器，它從 0 開始往上計數，0,1,2,3,4,5...。實際實作時，有一個k-位元的陣列在作此事，欲求在做了一連串(n次)計數後，這個計數器所作的計算複雜度是多少。

0. 鬆散分析(隨便亂算)
在最壞情況下時，作一次計數需複雜度O(k)，例如 01111111 再加 1 就變成 10000000，所以作 n 次計數需 $O(nk)$，因此 $T(n)=O(nk), T(n)/n = O(k)$


1. 聚集分析(aggregate analysis)
從計數 m 到計數 m+1 並不是每一個位元都會改變，而以前我們鬆散的估計就說有可能每一個位元都會改變 , 例如 01111111->10000000。事實上 仔細觀察：

• A[0] 位元每間個 $2^0$ 次 計數改變一次 
• A[1] 位元每間個 $2^1$ 次 計數改變一次 
• A[2] 位元每間個 $2^2$ 次 計數改變一次
  ...
• A[k] 位元每間個 $2^k$ 次 計數改變一次

$\frac{n}{2^0} + \frac{n}{2^1} + \frac{n}{2^2} +...+ \frac{n}{2^k} \leq 2n$
因此 $T(n) = O(2n) = O(n), T(n) / n = O(1)$


2. 記帳方法 (accounting method)

實際代價：
當任何一個位元
由 0 變 1 : 1 元成本
由 1 變 0 : 1 元成本

平攤代價：
當任何一個位元
由 0 變 1 : 2 元成本
由 1 變 0 : 0 元成本

計數器初始化時，每一個位元都是0，一旦開始計數，任何一位元由 0 變 1，會計師就記帳付2元，其中 1 元付給「時間複雜度」，另 1 元跟隨位元 1 變成存款。當此位元又由 1 變回 0 時，會計師就用這個位元 1 的存款付帳而不再花錢。

仔細觀察，任何一次計數頂多只有1個位元由0變1(付2元)，其他位元「不是不變，就是由1變0(不付錢)」，例如 0100111 再加 1 變成 0101000。所以任何一次計數，會計師頂多只付出 2 元，經過 n 次 計數，會計師頂多只付出 2n。因此 $T(n) \leq 2n, T(n) = O(n),T(n) / n = O(1)$

3. 勢能方法 (potential method)
定義勢函數 : $\Phi(D_i)$ = the number of 1’s in the counter after the i th operation
先確認勢函數，有$\Phi(D_n) \geq \Phi(D_0)$，$\Phi(D_0) ＝ 0$。

開始計算勢函數，例如：
after i-1 th operation : 00101111    $\Phi(D_{i-1}) = b_{i-1} = 5$
after i   th operation : 00110000    $\Phi(D_i) = b_i = 2$

一般化，其中$t_i$為i-1步的連續1的個數：
after i-1 th operation : ...011111    $\Phi(D_{i-1}) = b_{i-1}$
after i th operation : ...100000    $\Phi(D_{i-1}) = b_{i-1} - t_i + 1$

因此平攤分析為：
$C_i' = C_i + \Phi(D_i) - \Phi(D_{i-1})$
$= (t_i+1) + (b_{i-1} - t_i +1) – (b_{i-1})$
$= 2$

因此 $\sum C_i' = 2n，T(n) = O(n), T(n)/n = O(1)$






References

平攤分析 (amortized analysis) －算法導論學習筆記
http://blog.csdn.net/touzani/article/details/1696399

細說傾聽。技安聚星堂 - Amortized Analysis簡介
http://gian3211.blogspot.tw/2013/04/amortized-analysis_19.html

ustc.edu.cn - CHAPTER 18: AMORTIZED ANALYSIS
http://staff.ustc.edu.cn/~csli/graduate/algorithms/book6/chap18.htm