\( \newcommand{\ord}[1]{\mathcal{O}\left(#1\right)} \newcommand{\abs}[1]{\lvert #1 \rvert} \newcommand{\floor}[1]{\lfloor #1 \rfloor} \newcommand{\ceil}[1]{\lceil #1 \rceil} \newcommand{\opord}{\operatorname{\mathcal{O}}} \newcommand{\argmax}{\operatorname{arg\,max}} \newcommand{\str}[1]{\texttt{"#1"}} \)

2017年2月12日 星期日

[ 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$的部分

2017年2月7日 星期二

[ Minimum Arborescence / zhu_liu ] 朱劉算法 - 最小樹形圖

在有向圖中,給定一個點$r$作為生成樹的根,找出有向圖最小生成樹。


首先我們要能保證從$r$能夠走到圖上的所有點,這樣生成樹才會存在,這很簡單,一次DFS即可,再來是把圖上的所有自環移除,因為一顆樹裡面很明顯是不會有自環的。

之後就是算法的主要步驟了,可以先想一下,除了$r$以外的每一個點都有一條儘可能小的邊指向自己,最好的情況就是我們枚舉每一個點(除了根節點)並找到最小的一條指向這個點的邊,如果這些邊不構成有向環,就形成了一個所求的最小樹形圖。

但是實際上會出現環啊,但是這些環一定是獨立的,為甚麼呢?因為只有$|V|-1$條邊啊,只有是一棵樹的時候才會是連通的狀態。換句話說,如果圖連通了,就一定是最小樹形圖。

我們嘗試去換一些邊,使圖連通,在換的過程中我們總是選擇較小的邊,那麼得到的就是最小樹形圖。你可能會去枚舉一些邊把有向環拆掉,但是這樣的話可能會產生新的有向環,不是一個好做法。

朱劉算法就不直接去換邊,它也不去拆掉環,而是在不增加邊的情況下讓圖連通,怎麼做呢?就是用一個新的點代替原來圖的一個環(也就是所謂的「縮點」,和強連通分量有點像),並且修改跟這個環裡的點有關的邊的權值。

為何要修改邊的權重呢?當我們每更換一個點的入邊的時候我們就要去掉原來那個入邊,於是我們把這個點所有可能的入邊全部減少原來選取的那個入邊的權值,這樣每增加一條入邊無形中就刪去了原來那條邊。
上圖中紅色部分是要進行縮點的有向環

每個環上的點所有可能的入邊全部減少原來選取的那個入邊的權值

接著把環縮成一個點就可以了

假設我們想要把原來縮環之前3那條邊換成4那條邊,那我們換完的結果如下:
可以發現修改邊權後,不需要把邊刪掉,直接去計算選取邊的權重和就會和換邊的結果一樣
朱劉算法主算法的過程就是:找最小入邊->判斷有沒有環(沒有環就退出,算法成功)->縮點,改權值,如此反覆,一般來說為了方便不會去記錄縮點後虛擬節點裡包含了那些點,如果需要找出最小樹形圖包含的邊,就必須要真的去記錄他。

時間複雜度來說的話,用當時論文提出的實作方式,修改邊權的部分為$\ord{|E|}$,縮點最多執行$|V|-1$次,所以總複雜度是$\ord{|V|*|E|}$。
我自己有想了一個$\ord{|E| \; log \; |E|}$的方法,需要用到一種可以合併和把裡面所有元素加上某個值 的heap,又因為每個點最多只會連出去$|V|-1$條邊,也就是heap裡面只有$|V|$個元素是有用的,所以可以在heap大小為$2|V|$時把後$|V|$個元素刪掉,用斐式堆可以做到$\ord{|E|+|V| \; log|V|}$。

以下為$\ord{|V|*|E|}$的code:
接著是$\ord{|E| \; log^2|E|}$的code,使用啟發式合併(感謝59491、編譯器幫忙debug):
接著是$\ord{|E| \; log|E|}$的code,使用skew heap: