この記事は U-TOKYO AP Advent Calendar 2017 の8日目の記事です。
みなさん素晴らしい記事を書いていてハードルが上がりまくっていますが, 温かい目で見てくれたらと思います.
Union Find(経路圧縮あり)のならし計算量がアッカーマン関数の逆関数になることを知っている人は多いと思いますが, なぜそうなるのかは意外に知られていないのではと思い書きました. 思いっきり理論の話ですが, 根気強く読んでいただけるとうれしいです.
#はじめに
申し訳ないですが, この記事では Union Find のアルゴリズムを前提知識とします.
Union Find は実際に応用できる場面が多く, かつ実装が楽なアルゴリズムなので知らない方は知っておいて損はないと思います.
Union Findの説明スライドはこちらにあります.
参考までに自分の書いた Union Find のコードを載せておきます.
Find 関数の "$return\ parent[x] = Find(parent[x]);$" が経路圧縮を表しています.
class UnionFind {
private:
vector<int> parent, height;
public:
UnionFind(const int node_size)
: parent(node_size), height(node_size, 0){
for(int i = 0; i < node_size; ++i){
parent[i] = i;
}
}
int Find(const int x){
if(parent[x] == x){
return x;
}else{
return parent[x] = Find(parent[x]);
}
}
void Union(int x, int y){
x = Find(x), y = Find(y);
if(x == y){
return;
}
if(height[x] < height[y]){
parent[x] = y;
}else{
parent[y] = x;
if(height[x] == height[y]){
++height[x];
}
}
}
};
#アッカーマン関数
アッカーマン関数 $A_k(x): \mathbb{R} \rightarrow \mathbb{R}$ を以下で定義します.
\begin{align}
A_0(x) &= x+1 \\
A_{k+1}(x) &= A_k^x(x)
\end{align}
ここで, $A_k^i$ は $A_k$ の $i$ 重の合成関数とし, $A_k^0$ は恒等写像とします.
例えば, $A_1(x) = 2x$, $A_2(x) = x2^x$ というような関数になります.
またアッカーマン関数の逆関数 $\alpha(n)$ を以下で定義します.
\alpha(n) = \min \{ k \mid A_k(2) \geq n \}
アッカーマン関数 $A_k(x)$ は $k$ についてとても速く増加する関数であり, 例えば, $A_k(2)$ を例にとると,
| $k$ | $A_k(2)$ |
|---|---|
| 0 | 3 |
| 1 | 4 |
| 2 | 8 |
| 3 | 2048 |
| 4 | $約2^{6.62 \times 10^{619}}$ |
| のように $k=4$ の時点で膨大な数になります. 逆に言えばアッカーマン関数の逆関数 $\alpha(n)$ はその増加がとても遅くほぼ定数とみなせます. |
(注) "Efficiency of a Good But Not Linear Set Union Algorithm" [Tarjan 1975] や "Worst-Case Analysis of Set Union Algorithms" [Tarjan, LEEUWEN 1984] の解析で用いられているアッカーマン関数と定義が異なり, 以下で証明する事実は論文内の結果の簡単版となります. ただ基本的な計算量解析の考え方は同じです.
#準備〜変数の定義とその性質について〜
頂点集合を $V$, その頂点数を $n$ とします.
この頂点集合に対して Find 操作を $m\ (\ge n)$ 回, Union 操作を $n - 1$ 回任意の順番で行うとします.
以下の議論では Union は木を併合する操作, Find は木の根を探し, かつ道中のパス上の頂点の親を根に付け替える操作のことを言うことにします. つまり言いたいことは上のコードの関数名と異なり Union 操作は Find 操作を含まず, まったく別の disjoint な操作と考えます.
すると 1 回の Union 操作にかかる計算量は O$(1)$ なので, Union にかかる実際の計算量は全体で O$(n)$ です.
以降 Find 操作にかかる計算量のみを考え, それが全体として O$\left( (m + n) \alpha(n) \right)$ となることを示します.
まずは経路圧縮を行わない状況を考えます.
$T_t(u)$ を $t \ (0 \le t \le m+n-1)$ 回目の操作が終了した時点での $u$ を根とする部分木とし, また $height(T)$ は木 $T$ の高さを表すとします.
このとき $rank(u)$ を
rank(u) = height(T_{m+n-1}(u)) + 2
のように定めます. 言葉で書くと (全 $m+n-1$ 回の操作が終了した後の $u$ を根とする部分木の高さ) + 2 です. 次章ではこの $rank(u)$ を用いて計算量の証明を進めていきます.
続いて 2 つの Lemma を述べます(証明については章の最後に軽く書きます).
#####(Lemma 1)
任意の時刻 $t$, 任意の頂点 $u$ について以下が成り立つ.
\left| T_t(u) \right| \geq 2^{height(T_t(u))}
この Lemma は Union 操作で高さの大きい木に, 高さの小さい木を併合していくというように更新すると常に高さが $\log$ で抑えられるという事実に対応していて知っている方も多いかもしれません.
#####(Lemma 2)
$rank$ が $r$ となるような頂点集合 $S(r) = $ { $v \mid rank(v) = r$ } について以下が成り立つ.
\left| S(r) \right| \leq \frac{n}{2^{r-2}}
$rank$ が大きくなるにつれてその頂点数は指数的に減少する項で抑えられる, つまり $rank$ の小さい頂点はたくさんあって, 大きい頂点はほとんどないことを意味しています.
ここからは経路圧縮を行う状況について考えていきます.
まず $parent(u)$ を $u$ の親とします. 経路圧縮を行う状況では $u$ の親は時間により変化しうることに注意してください.
ただし, $rank(u)$ は前章で定義したものをそのまま用います. つまり "もし経路圧縮を行わなかったとしたときの (全 $m+n$ 回の操作後の頂点 $u$ を根とする部分木の高さ) + 2" とします. よって $rank(u)$ については時間により変化しないことに注意してください.
次に頂点 $u$ とその親 $parent(u)$ の間で "どれだけの経路圧縮が起きたか" の指標を $rank$ を用いて表すのですが, $rank(parent(u)) - rank(u)$ などのようにするのではなくアッカーマン関数 $A_k(x)$ を用いて以下のように $\delta(u)$ で定めます.
\delta(u) = \max \{ k \mid rank(parent(u)) \geq A_k(rank(u)) \} \tag{3}
$A_k(x)$ は上で定義したもので, また $\delta(u)$ は $u$ が親を持つ場合にのみ定義されます.
この $\delta(u)$ は時間に依存します. なぜなら $rank$ 関数自体は時間に依存しないものの, $parent(u)$ ($u$ の親) は上述の通り時間により変化しうるからです.
次にこの $\delta (u)$ が満たす性質を Lemma として述べます.
#####(Lemma 3)
$n$ が十分大きいとき, 親を持つ任意の頂点 $u$ について以下が常に成り立つ. ただし $\alpha(n)$ は前章で定義したものとします.
0 \le \delta(u) < \alpha(n)
この章の最後に Lemma 1 〜 Lemma 3 の証明を軽く書きます. 後回しして次の章を読んでいただいても全く問題ないです.
(Lemma 1 の証明)
$t$ についての帰納法を考えるとできます.
一番怪しい場合が時刻 $t$ に Union 操作が行われ, さらに木 $T_t(u)$ に $\left| T_t(u) \right| \ge \left| T_t(v) \right|$ となるような $T_t(v)$ が併合される場合です.
ただ, この場合も
\left| T_{t+1}(u) \right| \ = \left| T_{t}(u) \right| + \left| T_{t}(v) \right|
\ge 2^{height\left( T_t(v) \right)} + 2^{height\left( T_t(v) \right)}
= 2^{height\left( T_{t}(v) + 1\right) } = 2^{height\left( T_{t+1}(u) \right)}
より時刻 $t+1$ についても成り立ちます.
(Lemma 2 の証明)
$rank(u) = rank(v)$ となるような頂点 $u$, $v$ についてはそれらを根とする部分木 $T_{m+n-1}(u)$, $T_{m+n-1}(v)$ が交わらないことに注意すると,
\begin{align}
n &\geq \left| \bigcup _{rank(u)=r} T_{m+n-1}(u) \right| \\
&= \sum _{rank(u)=r} \left| T_{m+n-1}(u) \right| (\because rank \ が等しい頂点を根とする部分木どうしは \ disjoint) \\
&\geq \sum _{rank(u)=r} 2^{r-2} \ \ (\because Lemma \ 1) \\
&= S(r)・ \ 2^{r-2} \\
\end{align}
が成り立つので示せました.
(Lemma 3 の証明)
まず Lemma 2 より $rank(u)$ は高々 $\lfloor \log n \rfloor + 2$ であることが分かります.
すると十分大きな $n$ について
\begin{align}
n &> \lfloor \log n \rfloor + 2\\
&\geq rank(parent(u)) \\
&\geq A_{\delta(u)} (rank(u)) \\
&\geq A_{\delta(u)} (2) \ (\because rank(u) \ge 2) \\
\end{align}
が成り立つので, $\delta(u) < \alpha(n)$ が言えます.
また,
rank(parent(u)) \geq rank(u) + 1 = A_0(rank(u))
から $\delta(u)\geq 0$ も成り立ちます.
#Union Find の計算量について
Find($x$) は $x$ からその木の根 $r$ に向かってパスをたどり, そしてパス上の各頂点 $u$ について $parent(u)$ を $r$ に書き換えるという操作に対応します. そしてその計算量はパス上の各頂点について $\Theta(1)$ かかるため, パスの長さに比例します. 以下ではパス上の頂点を次の 2 つの場合に分けてこの Find にかかる計算量を考えていくことにします.
(Case 1) パス上の頂点 $u$ で $\delta(v) = \delta(u)$ となるような祖先 $v$ が存在するもの
(Case 2) パス上の頂点 $u$ で $\delta(v) = \delta(u)$ となるような祖先 $v$ が存在しないもの
ただし祖先に自分は含めないものとします. 根 $r$ については $\delta(r)$ が定義できないので (Case 2) に属するものとします.
初めに (Case 2) について説明します. こちらは比較的簡単です.
前章の Lemma 3 より $\delta(u)$ の取りうる値は $\alpha(n)$ 通りなので 1 回の Find 操作において (Case 2) にあてはまるパス上の頂点は根 $r$ も合わせて高々 $\alpha(u)$ + 1 個です. よって全 $m$ 回の Find 操作のうち (Case 2) で足しあげられる計算量は O$\left( m \alpha(n) \right)$ です.
次に (Case 1) にあてはまる頂点の数はのべ O$\left( n \alpha(n) \right)$ 個であることを示します.
以下では各頂点 $u$ について全 $m$ 回の Find 操作で何回 (Case 1) に入るか(何回 (Case 1) で足しあげられるか)を表す $\phi (u)$ を用いて計算量を評価をすることにします.
まず １ 番重要な Lemma を述べます(証明はこの章の最後に書きます).
#####(Lemma 4)
任意の頂点 $u$ についてその頂点が高々 $rank(u)$ 回 (Case 1) に入るごとに $\delta(u)$ は少なくとも 1 増加する.
この Lemma 4 と Lemma 3 の $0 \le \delta(u) < \alpha(n)$ を思い出すと, $\phi (u)$ は高々 $rank(u) \cdot \alpha(n)$ であることが言えます. 最後に $u \in V$ について $\phi (u)$ を $rank$ の値ごとに分けて足し上げてやると,
\begin{align}
\sum_{u \in V} \phi(u) &\le \sum_{u \in V} rank(u) \cdot \alpha(n) \\
&\le \sum_{r = 0}^{\infty} r \alpha(n) \frac{n}{2^{r-2}} (\because Lemmma \ 2) \\
&= n \alpha(n) \sum_{r = 0}^{\infty} \frac{r}{2^{r-2}} \\
&= 8 n \alpha(n) \\
\end{align}
ゆえに (Case 1) の場合について全体で計算量が O$\left( n \alpha(n) \right)$ となることが言え, (Case 1), (Case 2) を合わせて計算量は O$\left( (m + n) \alpha(n) \right)$ となります. 結論として Union Find の Find 操作にかかるならし計算量は O$\left( \alpha(n) \right)$ であることが示せました.
(Lemma 4 の証明)
時刻 $t$ の Find 操作で頂点 $u$ が (Case 1) に入る場合を考えます.
頂点 $u$ は (Case 1) に属することから $\delta(v) = \delta(u) = k$ を満たす頂点 $v$ が $u$ の祖先に存在します.
また関数 $\delta$ の定義から
rank(parent(u)) \geq A_k(rank(u)) \\
rank(parent(v)) \geq A_k(rank(v))
が成り立ちます. ここでさらにある整数 $i$ ($\ge 1$) について
rank(parent(u)) \geq A_k^i(rank(u))
が成り立つと仮定します. するとこの Find 操作時の $u, v$ を含む木の根を $r$ としたとき
\begin{align}
rank(r) &\geq rank(parent(v)) \\
&\geq A_k(rank(v)) \\
&\geq A_k(rank(parent(u))) \\
&\geq A_k(A_k^i(rank(u))) \\
&= A_k^{i+1}(rank(u))
\end{align}
が成り立ちます.
証明中で親の存在する任意の頂点 $x \in V$ について必ず $rank(parent(x)) \ge rank(x)$ が成り立つという事実を暗に用いています. また頂点 $r$ は時刻 $t+1$ において $parent(u)$ となるので時刻 $t+1$ では
rank(parent(u)) \geq A_k^{i+1}(rank(u))
が成り立ち, $A_k(rank(u))$ の肩が 1 増えます.
一度頂点 $u$ が根でなくなると, 以降再び頂点 $u$ が再び根になることはないです.つまり $\delta(u)$ が今後定義されなくなることはないです. また時刻 $t$ において $rank(parent(u)) \geq A_k^{i}(rank(u))$ のもとで、 (Case 2) の場合で数えられたときも時刻 $t+1$ において必ず $rank(parent(u)) \geq A_k^{i}(rank(u))$ が成り立ちます.
よって, 頂点 $u$ が (Case 1) に高々 $rank(u)$ 回入ると,
rank(parent(u)) \geq A_k^{rank(u)}(rank(u))=A_{k+1}(rank(u))
が成り立ち, $\delta(u) \ge k + 1$ となることから $\delta(u)$ は少なくとも 1 増えます.
#参考文献
http://www.cs.cornell.edu/courses/cs6110/2014sp/Handouts/UnionFind.pdf
https://www.cs.cmu.edu/~avrim/451f11/lectures/lect1020.pdf
https://massivedatasets.files.wordpress.com/2011/02/amortizedslidesf111.pdf
http://e-maxx.ru/bookz/files/dsu/Efficiency%20of%20a%20Good%20But%20Not%20Linear%20Set%20Union%20Algorithm.%20Tarjan.pdf