2015年6月22日 星期一

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






技術提供:Blogger.