経路圧縮のみを用いた union-find の計算量解析

union-find の高速化テクニックとして経路圧縮は有名である。しかし、その計算量解析は有名ではないと思う。

そこで、この記事では経路圧縮のみを用いた union-find の計算量解析を行う。計算量解析にはポテンシャル解析を用いるため、予備知識としてポテンシャル解析が必要である。ポテンシャル解析に関してはChris Okasakiの『Purely Functional Data Structures』が分かりやすい。

経路圧縮のみの union-find

界隈では有名なため、擬似コードを示すだけに留めておく。

int par[N];

int find(int x) {
    if (x == par[x]) return x;
    return par[x] = find(par[x]);
}

void unite(int x, int y) {
    par[find(x)] = find(y);
}

解析

親ポインタの張り替え回数の上界を、ポテンシャルを用いて評価する。ポテンシャルを以下のように設定する。

サイズ
 \mathrm{size}(x)。頂点 x の配下にある頂点数
頂点ポテンシャル
 \phi(x)=\log(\mathrm{size}(x))
ポテンシャル
\Phi=\sum_{x} \phi(x)

やや天下り的だが、 \log の底は 4 にする。これは途中の帳尻を合わせるためである。

find を実行したとき、一番最初に親ポインタが張り変わるのは、根の直下にある頂点――ここでは頂点\(x\)――である。張り替えにより図のように変化する。

f:id:pekempey:20170207013202p:plain

頂点ポテンシャルが変化するのは頂点 \(x\) だけであるため、 \Delta\Phi=\Delta\phi(x) である。ならしコストは、(実コスト)+(ポテンシャルの変化量)であるから、

\begin{align}
amortized\ cost = 1+\log\alpha-\log(\alpha+\beta)
\end{align}

である。突然だが、以下の不等式を示す。

\begin{align}
amortized\ cost \le \log(\mathrm{size}(x))-\log(\mathrm{size}(y))
\end{align}

上記の不等式を具体的に書けば次の不等式になる。

\begin{align}
1+\log\alpha-\log(\alpha+\beta) \le \log(\alpha+\beta) - \log\beta
\end{align}

これはJensenの不等式を用いて示せる。

find の実行過程で、\(x,y,z\)の順に次々と根に繋ぎ直される。先程示した不等式を用いることで、この amortized cost は以下のように評価できる。

\begin{align}
{}&\log(\mathrm{size}(a))-\log(\mathrm{size}(b)) \\
{}+&\log(\mathrm{size}(b))-\log(\mathrm{size}(c)) \\
{}+&\log(\mathrm{size}(c))-\log(\mathrm{size}(d)) \\
\vdots
\end{align}

ほとんどの項が打ち消されるため、コストは  \log n で抑えられることが分かる。したがって、find の計算量は \(O(\log n)\) amortized である。

unite の計算量解析は容易である。\(y\)の親を\(x\)に張り替えるとき、\(x\)は根であるためポテンシャル変動は \(x\) のみで起こる。ポテンシャルの変化量は \(\log n\) で抑えられるから \(O(\log n)\) amortized である。