Union Find の計算量を解説する。

二項木とは

いくつかの種類の Union Find において最悪ケースを与える二項木 \(B_k\) を最初に紹介する。
二項木を

• \(B_0\) は 1 頂点からなる根付き木
• \(B_{k+1}\) は、根の子をそれぞれ新たな根とする部分木が \(B_0,B_1,\ldots,B_{k}\) である根付き木

と定義する。\(B_0,B_1,B_2,B_4\)を図示すると下図のようになる。

帰納法から二項木 \(B_k\) は頂点数 \(2^k\) 、高さ \(k\) である。

帰納法から \(B_{k+1}\) の構成方法は図の通り 3 つある。 union by rank, union by size いずれでも \(B_k\) と \(B_k\) を Union すると \(B_{k+1}\) ができるから、Union Find の \(2^{k}\) 回の合併で \(B_k\) を作りだすことができる。

Union by Size の計算量

Union by Size とは、根付き木 A, B を Union するとき、頂点数の小さい方の木をもう一方の木の根の子とする方法である。

その構成方法から \(2\mathrm{size}(u) \leq \mathrm{size}(\mathrm{parent}(u))\) が成り立つ。従って \(O(\log{n})\) である。二項木 \(B_k\ (2^k \sim n)\ \) は、高さ \( \Theta(\log n) \) であるから最悪ケースを与える。

Union by Rank の計算量

Union by Rank とは、根付き木 A, B を Union するとき、rank の小さい方の木をもう一方の木の根の子とする方法である。rank は（経路圧縮しないときの）木の高さとして定義する。

まず、ランク \(r\) 以上の頂点を根とする部分木のサイズは \(2^r\) 以上であることを帰納法で示す。

ランク \(r\) の木のサイズについて \(2^r \leq n\) より \(r \leq \lfloor \log_2 n \rfloor \)。ランクは高さと一致していたから find クエリと union クエリは共に \(O(\log n)\) となる。二項木 \(B_k\ (2^k \sim n)\ \) は、高さ \( \Theta(\log n) \) であるから最悪ケースを与える。

経路圧縮の計算量解析

経路圧縮(path compression) では Union が \(O(1)\)、Find がならし \(O(\log N)\) であることを示す。path halving, splitting は同じように解析できるので扱わない。

時刻 \(t\) における頂点 \(i\) の部分木のサイズを \(\sigma_i(t)\)、ポテンシャル関数を \(\Phi(t):=4\sum_{i=1}^n \log_2 \sigma_i(t)\) と置く。\(0 \leq \Phi(t) \leq 4n\log_2 n\) かつ \(\Phi(0)=0\) である。

Union では繋ぎ合わせる根のポテンシャルの寄与しか変化せず、一回当たり \(O(\log N)\) しか増加しない。Union では内部で 2 回 Find を行うから、Union でのポテンシャルの増分は Find に割り当てればよい。

時刻 \(t\) の Find において辿るパス上の頂点を根から遠い順に \(\sigma_1,\sigma_2,\ldots,\sigma_k\) と置く（上図は k=5 の場合）。Find には根を見つけるのに \(k\) ステップ、根を繋ぎ替えるのに \(k-1\) ステップの合計 \(2k-1\) ステップかかる。ポテンシャルの変化量は
$$
\begin{align}
H(t)-H(t-1)
=&4\sum_{i=2}^{k-1} \left(\log_2(\sigma_{i}-\sigma_{i-1})-\log_2\sigma_{i}\right)\\
=&4\sum_{i=2}^{k-1} \log_2\left(1-\frac{\sigma_{i-1}}{\sigma_i}\right)\\
\leq & – 4\sum_{i=2}^{k-1} \frac{\sigma_{i-1}}{\sigma_i}\
\end{align}
$$
で抑えられる。\(\frac{\sigma_{i}}{\sigma_{i+1}} \leq 1/2\)なる \(i\) が \(m\) 個あるとする。\(1 \leq \sigma_1 < \sigma_2 < \ldots < \sigma_k \leq n\) だから、\(2^m \leq \sigma_k \leq n\) となり、\(m \leq \log_2 n\)。従って

\(-4\sum_{i=2}^{k-1} \frac{\sigma_{i-1}}{\sigma_i} < -4\cdot\frac{1}{2}(k-2-m) < -2k+4+4\log_2n\)

より \(H(t)-H(t-1)+2k-1=O(\log n)\) となるから Union はならし \(O(\log n)\) である。

Path Compression の最悪ケース

画像の操作を繰り返すと Union がならし \(\Theta(\log n)\) となる。

Union by Rank, Size と経路圧縮の組み合わせ

Union by Rank (または Union by Size) と経路圧縮を組み合わせたとき、クエリ当りの計算量がアッカーマンの逆関数 \(O(\alpha(n))\) となることが知られている。しかし、この証明は結構難しいので、評価を弱めて iterated logarithm \(O(\log^*(n))\) で抑えられることを示そう[4]。iterated logarithm は $$x \in [\underbrace{b^{b^{\cdot^{\cdot^{b}}}}}_{y-1個}, \underbrace{b^{b^{\cdot^{\cdot^{b}}}}}_{y個})$$ に対して \(\log_b^*(x)=y\) である。\(y = 0\) のとき、\(y-1=-1\) 個となって壊れるので、\(x < 1\) に対しては \(\log^*(x)=0\)と定める。\(\log^*(n)\) は \(\log(n)\) よりずっと小さい。

次の定理が Union by Rank のときに成り立つことは、「Union by Rank の計算量」の節で示した。Union by Size の場合について示す。

この定理を元に次の定理を示そう。

最終的に全ての頂点が Union によって連結になると仮定しても、計算量評価の一般性を失わない。Find によって、与えられた頂点から根まで辿るパスの辺の数を評価すれば良い。

頂点の集合 \(s_k := \{v | \log_2^*(\mathrm{rank}(v))=k\}\) を定義する。Find によって辿るパス上の辺 (u, v) について、 u と v が異なる集合 \(s_i\) に属しているとする。パス上の頂点の rank は根に近づくにつれて狭義単調増加するから、このような u, v はクエリ当り \(O(\log^*(n))\) 個しかない。

従って、同じ集合 \(s_i\) 内の２頂点を端点とする辺がいくつ Find のパスに含まれるか評価すれば良い。\(B:=\underbrace{2^{2^{\cdot^{\cdot^{2}}}}}_{y-1個}\) と置く。rank r の頂点は高々 \(n/2^r\) 個しかないので、\(s_i\) のサイズは \(\frac{n}{2^{B}}+\frac{n}{2^{B+1}}+\ldots+\frac{n}{2^{2^B-1}} < \frac{2n}{2^B}\) で抑えられる。パス上の頂点 u が根でも根の子でもないとする。すると、経路圧縮で頂点 u の親は rank が増加する。従って、Find のパスに u が含まれるクエリのうち、u の親が u と同じ \(s_i\) に含まれるものは高々 \(2^B – B + 1 < 2^B\) 個しかない。全体では \(\sum_i 2^B \times \frac{2n}{2^B} = O(n \log^*n)\) 個である。Find のパス上の頂点のうち、根または根の子は高々２個しかないので、そのような頂点を端点に持つ辺の個数は計算量評価で無視しても良い。

以上より、Union by Rank, Size と経路圧縮を組み合わせるとならし \(O(\log^*(n))\) になることが示された。

参考文献

1. Kevin Wayne 氏の授業スライド
   • 図が豊富で分かりやすいです。アルゴリズムの挙動自体が分からないという場合はこちらを見ると良いと思います。
2. Alternative path compression techniques. van Leeuwen, J. van der Weide, R. (1977)
   • paht halving を提唱した論文。計算量解析の部分を勉強しました。彼らは path halving + link by rank はクエリ当たりの計算量が iterated logarithm \(\Theta(\log^* n) \) だと予想していたようです（実際はアッカーマンの逆関数）。
3. Fischer, Michael J. “Efficiency of equivalence algorithms.” Complexity of Computer Computations. Springer, Boston, MA, 1972. 153-167.
   • path compression の計算量解析のために二項木を導入した論文。二項木のフラクタルな構造が面白いと思いました。
4. Hopcroft, John E., and Jeffrey D. Ullman. “Set merging algorithms.” SIAM Journal on Computing 2.4 (1973): 294-303.
   • 計算量が iterated logarithm で抑えられることを示した論文。
5. Disjoint-set data structure – Wikipedia