[ Amortized analysis - Potential method ] 平攤分析 - 勢能方法

對於一個stack操作，pop和push都是$\ord{1}$的，這很好理解，現在定義了一個新的操作，pop_all，表示pop stack內的所有元素，顯然這是一個$\ord{N}$的操作。那我們進行一連串的push、pop、pop_all的複雜度上界是多少呢？

根據big-O的特性，因為pop_all是$\ord{N}$的，我們把每個操作都當作$\ord{N}$來看，執行$N$次操作的總複雜度就會是$\ord{N^2}$。這沒有錯，但怎麼想都覺得怪怪的，怎麼可能一直執行pop_all呢？執行一次pop_all之後stack就沒有元素了耶！

這三種操作不是平行的，而是互相影響的。換言之，你每次的push創造“機會”給pop和pop_all。pop和pop_all才能“消費”著這些機會，不存在無限制的消費。

因此這個複雜度是高估的，那要究竟怎麼真正去計算$N$次操作的總複雜度呢？

勢能方法

對於一個資料結構$DS$，我們定義$\Phi(DS)$表示$DS$的“勢能”，而且要保證在任何情況下$\Phi(DS) \geq 0$。

通常$\Phi(DS)$我們會定義他是$DS$的某個性質，像是元素個數啦，如果是二元樹的話可能是所有節點左子樹大小減右子樹大小的絕對值的總和啊、或是葉節點的個數啊...各種東西都可以當作是$DS$的勢能。

 那$\Phi(DS)$能用來幹甚麼？我們定義$\Phi_0$表示$DS$在還沒有進行任何操作時的勢能，假設有$N$個操作，第$i$個操作的時間花費為$t_i$，這個操作結束之後的勢能為$\Phi_i$，$i>0$，我們定義第$i$個操作的均攤時間$a_i=t_i+C(\Phi_i-\Phi_{i-1})$，這裡$C>0$是一個常數

可以發現總均攤花費時間：
$$
\sum^{N}_{i=1}a_i=\sum^{N}_{i=1}(t_i+C(\Phi_i-\Phi_{i-1})) \\
=(t_1+t_2+...+t_n)+C(-\Phi_0+(\Phi_1-\Phi_1)+(\Phi_2-\Phi_2)+...+(\Phi_{n-1}-\Phi_{n-1})+\Phi_n) \\
=\sum^{N}_{i=1} t_i +C(\Phi_N-\Phi_0)
$$
最後得到：
$$
\sum^{N}_{i=1}t_i=\sum^{N}_{i=1}a_i-C(\Phi_N-\Phi_0)
$$
這個特性告訴我們，只要好好選擇$\Phi(DS)$函數，就可以在$\ord{\sum^{N}_{i=1}t_i}$很難直接求的情況下透過$\ord{\sum^{N}_{i=1}a_i-C(\Phi_N-\Phi_0)}$求出$\ord{\sum^{N}_{i=1}t_i}$。

證明範例

有了勢能方法，可以很輕鬆的用它來計算一些資料結構操作的均攤複雜度。

以剛剛stack的例子來說，我們設定stack $S$它的勢能函數$\Phi(S)$為$S$的元素個數，可以確定$\Phi_0=0$且$\Phi(S) \geq 0$。

我們設一次的push、一次的pop花費一單位的時間，並設常數$C=1$，在第$i$次操作：

• 如果是push操作的話$t_i=1$，stack的元素個數增加$1$
  因此$\Phi_i-\Phi_{i-1}=1$
  $a_i=t_i+\Phi_i-\Phi_{i-1}=1+1=2$
• 如果是pop操作的話$t_i=1$，stack的元素個數減少$1$
  因此$\Phi_i-\Phi_{i-1}=-1$
  $a_i=t_i+\Phi_i-\Phi_{i-1}=1-1=0$
•  如果是pop_all操作的話$t_i=n$，stack的元素個數減少$n$
  因此$\Phi_i-\Phi_{i-1}=-n$
  $a_i=t_i+\Phi_i-\Phi_{i-1}=n-n=0$

$a_i$的最大值是$2$，經過$N$次操作之後$\Phi_N-\Phi_0$的最小值為$0$
可以知道：
$$
\ord{\sum^{N}_{i=0}t_i}=\ord{\sum^{N}_{i=1}a_i-(\Phi_N-\Phi_0)}=\ord{2N+0}=\ord{N}
$$
因此經過$N$次stack的任何有效操作之後，總花費的時間為$\ord{N}$，這才是我們滿意的結果。

對了，通常來說$\Phi_0$都會是0，因此在大部分的情況下：
$$
\ord{\sum^{N}_{i=0}t_i}=\ord{\sum^{N}_{i=1}a_i}
$$
所以大部分的證明都會忽略掉$\Phi_N-\Phi_0$的部分