Skip to content →

最悪計算量を最小化した Union Find

Union Find は link by size (または link by rank) と経路圧縮を組み合わせることで、各操作をならし \(O(\alpha(n))\) にできることが知られている(\(\alpha\) はアッカーマンの逆関数、\(n\) は頂点数)。このならし計算量は理論的に最良であるが、最悪計算量は \(O(\log n)\) になる(例えば二項木の Find :Union Find の計算量 (1))。そこで、この記事では理論的に最良な最悪計算量 \(O(\log n/\log\log n)\) を実現する Union Find を紹介する[1]。

アルゴリズムの解説

次の三つの条件を満たす根付き木を k-UF 木 (k > 1) と定義する。

  1. 根と葉以外の頂点は \(k\) 個以上の子を持つ。
  2. 根は2個以上の子を持つ。
  3. 葉の深さは全て等しい。

このような木は葉の数 \(n\) に対し高さが \(O(\log_k n)\) である。特に \(k = O(\log n)\) とすると、高さが \(O(\log n/ \log \log n)\) になって、Find の計算量削減が期待できる。条件2は最悪計算量の改善に非本質なので、この記事では忘れてもよい。

k-UF 木の根を集合の名前を表す頂点、葉を集合の元を表す頂点とする。それ以外の頂点は根と葉を繋ぐ以外に意味のない頂点とする。根に載せる頂点の名前は代表元のラベルにすることが多い。二つの集合を合併(Union)し新たな集合を作るとき、対応する二つの k-UF 木を合併して新たな k-UF 木を作る。また、ある元 v の属する集合の名前を得る(Find)ときには、v に対応する k-UF 木の葉から根まで親を辿る。

Find の計算量は木の高さ \(O(\log_k n)\) で抑えられる。Union の計算量については、次の事実が成り立つ。

2つの素集合 a, b を合併して新たな集合 c を作る操作を Union Find 上で行う。このとき、a, b を表す k-UF 木 A, B を合併して c を表す k-UF 木が \(O(k+\log_k n)\) で構築できる。
証明:木の高さ(height)は \(O(\log_k n)\) で分かるから、一般性を失わず height(A) ≦ height(B) を仮定できる。A の根を r 、A と高さの等しい B のいずれかの頂点を v とする。v は B の根から子を辿れば \(O(\log_k n)\) で見つかる。

次のようにすれば、A と B を合併した k-UF 木が \(O(k)\) で構築できる:

  1. v が B の根でない場合:
    1. r の子の数が k 以上ならば r を v の兄弟として繋ぎ替える。
    2. r の子の数が k 未満ならば r の子を r から分離して v の子に繋ぎ替える。r は破棄する。
  2. v が B の根である場合、A より B の方が根の子の数が多いと仮定しても一般性を失わない。
    1. r の子の数が k 以上ならば r と v を子とする新しい根を作る。
    2. r の子の数が k 未満ならば (i) の (2) と同様である。

それぞれの場合を図にすると次のようになる。
以上で Union が \(O(k+\log_k n)\) でできた。

初期状態の 1 元集合は k-UF 木ではないが、同じように合併できる。最悪計算量 \(O(k+\log_k n)\) は \(k = \log n / \log \log n \) のとき最小量 \(O(\log n /\log \log n)\) を取る。最悪計算量 \(O(\log n /\log \log n)\) の Union Find ができた。

ある種の Union Find っぽい問題設定ではこの計算量が Union Find の最悪計算量を最小化した値として最良であることが示せる。詳しくは参考文献を参照せよ。

参考文献

  1. Blum, Norbert. “On the single-operation worst-case time complexity of the disjoint set union problem.” SIAM Journal on Computing 15.4 (1986): 1021-1024.
永続 Union Find を調べていて、このアルゴリズムを知りました。永続化においては、ならし計算量は関係ないからです。シンプルなアルゴリズムで面白いですね。実装してみました(コード)。実装も軽い。

Published in データ構造

Comments

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

CAPTCHA