読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

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

スプレー木がうまくいくのだから、union-find も似たような理由でうまいくのではと思い解析に挑戦してみました。スプレー木と同じポテンシャルの設定で解析できたのでメモしておきます。特に何かを参考にしたわけではないので間違っていたらごめんなさい。

ポテンシャル解析を知っていることを前提としています。その発想どこからでてきたの?みたいなのは大体スプレー木の解析で使われている考え方を引っ張ってきてます。

ポテンシャル解析については以下の記事に書きました。

pekempey.hatenablog.com

上の記事の説明はアルゴリズムイントロダクションの2巻に書いてあるので、そっちを読んだほうがいいかもしれません。
実を言うと、自分は『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 にしておくと帳尻が合うので、そうしておく。

さて、実際に張り替えてみよう。張り替えの様子を下図に示した。

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}

証明は log の凸性を用いて幾何的に行える。

頂点 y の親ポインタの張り替えのならしコストは求まった。しかし一般に親ポインタの張り替えは複数回行われる。たとえば、次に頂点 z の親ポインタの張り替えが行われるかもしれない。しかし、そのコストはたかだか  \log(\mathrm{size}(y))-\log(\mathrm{size}(z)) である。一般に find 経路 a,b,c,d,... に対して、全体のならしコストの上界は

\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 の計算量は求まった。unite の方は自明だろう。