Union Find
作成日：2019.01.17
最終更新日：2019.01.17
目次
計算量
要素の数を$N$とすると、ならし計算量は$O(\alpha(N))$となる。但し$\alpha$はアッカーマン関数の逆関数であり、これは定数とみなしても差し支えないほど増加が非常に遅い。
但し経路圧縮のみの場合はならし計算量が$O(\log N)$、辺のつなぎ方の工夫のみの場合は最悪計算量が$O(\log N)$となる。
計算量解析(経路圧縮のみ)
各操作にかかる時間は根までたどったパスの長さに線形であるから、経路圧縮を行うごとにたどったパスの根以外の頂点の数を数えて総和をとることで計算量を考えられる。
要素を表す頂点$v$に対して、${\rm rank}(v)$を経路圧縮も行わずに操作をすべて行った時にできる森における$v$の部分木の高さとする。
すると$u$が$v$の祖先である時、${\rm rank}(u) \gt {\rm rank}(v)$ である。
また経路圧縮が起きるたびに変化する指標${\rm level}(v)$を、$v$が根の時は$0$、そうでない時はその時点での$v$の親を$p_v$として$\lfloor \log ({\rm rank}(p_v)-{\rm rank}(v)) \rfloor$ ($\log$の底は$2$、以下同様)で定義する。
この時、$0 \leq {\rm rank}(v) \lt N$ より $0 \leq {\rm level}(v) \leq \lfloor \log N \rfloor$ である。
経路圧縮が起きるたびに圧縮されたパス上の根以外の頂点を、根以外の祖先に自身と同じ${\rm level}$の頂点が存在するかで分類する。
存在しない頂点(a)は${\rm level}$の種類の数以下、すなわち$(\lfloor \log N \rfloor+1)$個以下である。
また存在する頂点(b)は${\rm level}$が$1$以上増加する。
なぜなら$v$の先祖$u$で${\rm level}(u) = {\rm level}(v)$となるものが存在する時、$v$の新たな親を$t$とすると、
であるからである。このことから(b)として経路圧縮が行われるのは頂点ごとに高々$\lfloor \log N \rfloor$回であることが分かる。
よって操作時にたどったパスの根以外の頂点の数の総和は、根までたどった回数を$M$として$(M(\lfloor \log N \rfloor+1)+N\lfloor \log N \rfloor)$以下である。
これは操作回数が$N$と同程度以上であるならば、ならし計算量が$O(\log N)$となることを示している。
参考：Worst-Case Analysis of Set Union Algorithms (Tarjan,Leeuwen)
計算量解析(辺のつなぎ方の工夫と経路圧縮)
非負整数$m,n$を引数にとるアッカーマン関数$A(m,n)$は以下のように定義される関数である。
$s \leq t$ ならば $A(m,s) \leq A(m,t)$ であることは帰納的に示すことができる。
また$\alpha(n)$を $\alpha(n) := \min\{k \geq 0 \ | \ A(k,1) \geq n\}$ と定義すると、これはアッカーマン関数の逆関数となっている。
経路圧縮のみの時と同様、たどったパスの根以外の頂点の数を数えて総和をとることで計算量を考える。
要素を表す頂点$v$に対して、${\rm rank}(v)$を経路圧縮を行わずに操作をすべて行った時にできる森における$v$の部分木の高さに$1$を加えたものとする。
すると$u$が$v$の祖先である時、${\rm rank}(u) \gt {\rm rank}(v)$ となる。
このことと高さが$h$の木には少なくとも$2^h$個の頂点があることを合わせると、${\rm rank}$が$r$の頂点は高々$\frac{N}{2^{r-1}}$個しかないことが分かる。
さらに、辺のつなぎ方から木の高さが$\lfloor \log N \rfloor$以下となるので、$1 \leq {\rm rank}(v) \leq \lfloor \log N \rfloor + 1$ である。
また経路圧縮が起きるたびに変化する指標${\rm level}(v)$を、$v$が根の時は$0$、そうでない時はその時点での$v$の親を$p_v$として${\rm rank}(p_v) \geq A(k,{\rm rank}(v))$ を満たす最大の$k$で定義する。
${\rm rank}(p_v) \geq {\rm rank}(v) + 1 = A(0,{\rm rank}(v))$ より${\rm level}$が定義できていることに注意する。
この時
であるから、$0 \leq {\rm level}(v) \leq \alpha(N)$ となる。
経路圧縮が起きるたびに圧縮されたパス上の根以外の頂点を、根以外の祖先に自身と同じ${\rm level}$の頂点が存在するかで分類する。
存在しない頂点(a)は${\rm level}$の種類の数以下、すなわち$(\alpha(N)+1)$個以下である。
以下、存在する頂点(b)について考える。
$l = {\rm level}(v)$ とすると
より、${\rm rank}(p_v) \geq A(l+1,i)$ となる最大の非負整数$i$をとることができる。 $i \geq {\rm rank}(v)$ である時、${\rm level}(v) \geq l+1$ となるので、$0 \leq i \lt {\rm rank}(v)$ であることに注意する。 この時$v$の先祖$u$で${\rm level}(u) = l$となるものが存在し、$v$の新たな親を$t$とすると、
となる。以上のことから頂点$v$が(b)として経路圧縮を${\rm rank}(v)$回行われると、${\rm level}(v)$は1以上増加することが分かる。 ${\rm level}$は$\alpha(N)$回しか上がらないから、頂点$v$が(b)として経路圧縮を行われるのは、${\rm rank}(v)(\alpha(N)+1)$回未満である。 ところで${\rm rank}$が$r$となるような頂点は$\frac{N}{2^{r-1}}$個以下であったから、(b)として経路圧縮が行われる頂点の延べ数は
で抑えられる。
以上より操作時にたどったパスの根以外の頂点の数の総和は、根までたどった回数を$M$として $(4N+M)(\alpha(N)+1)$ 未満である。
これは操作回数が$N$と同程度以上であるならば、ならし計算量が$O(\alpha(N))$となることを示している。
参考：Analysis of Union-Find (lecture by Cornell University)