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_3,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 \sigma_i(t)\) と置く。\(0 \leq \Phi(t) \leq 4n\log 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(\sigma_{i}-\sigma_{i-1})-\log\sigma_{i}\right)\\
=&4\sum_{i=2}^{k-1} \log\left(1-\frac{\sigma_{i-1}}{\sigma_i}\right)\\
\leq & – 4\sum_{i=2}^{k-1} \frac{\sigma_{i-1}}{\sigma_i}\
\end{align}
$$
で抑えられる（最後の不等号 \(\log(1-x) \leq -x\) は原点での接線より）。\(\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 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 n\)

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

Path Compression の最悪ケース

\(k=\Theta(\log(n))\) として、画像の操作を \(\Theta(n)\) 回だけ繰り返すと Union と Find がならし \(\Theta(\log n)\) となる。

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

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

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

この定理から、頂点の個数は葉から遠いほど指数関数的に抑えられ、次の定理が成り立つ。

例えば、完全 \(m\) 分木 (\(m \geq 2\)) がこの条件を満たす。逆に、Path Comparession の worst case で上げた例は高さが \(\Theta(n)\) あるので満たさない。長さ \(\log(n)\) のパスが \(n/\log(n)\) 本だけ根に接続した木も駄目である。定理を証明する。

最終的に全ての頂点が 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))\) になることが示された。

同じことだが、分割統治法で捉えることもできる[6]。高さ \(h\) の森に対して、高さ \(\log_2(h)\) を境に上下に分割する（下図）。高さ \(\log_2(h)\) 以上の頂点の数は \(\sum_{r=\log_2(h)}^h n/2^r < 2n/h\) で抑えられる。この頂点同士を端点に持つ辺が Find のパスに含まれるのは \(O(h\times (2n/h)) = O(n)\) 回。高さ \(\log_2(h)\) 以上の頂点と未満の頂点を端点に持つ辺は 各Find のパスに高々 1 回しか含まれないから、操作全体で \(O(n)\) 個。高さ \(\log_2(h)\) 未満の森に対して分割統治を繰り返す。分割統治は \(O(\log^*(n))\) 回繰り返せば終了するので、全体で \(O(n\log^*(n))\) 時間。 これは \(i\) の降順に \(s_i\) を評価していることと対応する。

findを繰り返したときの計算量

union find で \(\Theta(n\log(n))\) 回 find ( union 内部のそれを含む）すると、ならし \(O(1)\) になる。path compression を無視した仮想的な木は、高さが \(O(\log(n))\) になるから。Gabowらの最小全域有向木問題の高速化に Union Find のオーバーヘッドが掛からない理由がこれだった。

参考文献

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
6. Seidel, Raimund, and Micha Sharir. “Top-down analysis of path compression.” SIAM Journal on Computing 34.3 (2005): 515-525.

関連記事

1. 最悪計算量を最小化したUnion Find
   • 永続化したい場合やオンラインで処理したい場合、ならしではなく最悪計算量を最小化した方が良いことがあります。ならし計算量 \(O(\alpha(n))\) の Union Find は、最悪計算量が \(\Theta(\log(n))\) になることがあります。この記事では最悪計算量 \(O(\log(n)/\log\log(n))\) の Union Find を紹介しています。