c++ - Union-Find データ構造

Question

多くの問題について、union-find データ構造を使用することをお勧めします。私はそれについて読んで、それがどのように実装されているかを考えてみました (C++ を使用)。私の現在の理解では、それはセットのリストに過ぎないということです。したがって、要素が属するセットを見つけるには、n*log n操作が必要です。ユニオンを実行する必要がある場合は、マージする必要がある 2 つのセットを見つけて、set_unionそれらに対して a を実行する必要があります。これは私にはあまり効率的ではないようです。このデータ構造についての私の理解は正しいですか、それとも何か不足していますか?

Answer 1

データ構造は、枝が逆になっているツリーとして表すことができます (枝は下を指すのではなく、親に向かって上を指し、子とその親をリンクします)。

私の記憶が正しければ、（簡単に）表示できます。

• そのパス圧縮 (セット A の「親」を検索するときはいつでも、パスを「圧縮」して、これらへの将来の各呼び出しが時間 O(1) で親を提供するようにします) は O(log n ) 呼び出しごとの複雑さ。

• そのバランス (各セットに含まれる子の数をおおよそ追跡し、2 つのセットを「結合」する必要がある場合は、子の数が少ない方を最も多い方の子にします) も O(log n) 呼び出しごとの複雑さ。

より複雑な証明は、両方の最適化を組み合わせると、α(n) と書かれた逆アッカーマン関数である平均的な複雑さを取得することを示すことができます。これは、この構造に対するタージャンの主な発明でした。

後に、いくつかの特定の使用パターンでは、この複雑さが実際には一定であることが示されたと思います (ただし、すべての実用的な目的では、アッカーマンの逆数は約 4 です)。Union-Find のウィキペディアのページによると、1989 年に、同等のデータ構造の操作ごとの償却コストは Ω(α(n)) であることが示され、現在の実装が漸近的に最適であることが証明されました。

Answer 2

適切なunion-findデータ構造は、すべての検索中にパス圧縮を使用します。これによりコストが償却され、各操作はアッカーマン関数の逆関数に比例します。これにより、基本的に一定になります（ただし完全ではありません）。

ゼロから実装する場合は、ツリーベースのアプローチを使用することをお勧めします。

Answer 3

単純な共用体セット構造は配列 (要素 -> セット) を保持し、どのセットを一定の時間で見つけるかを決定します。それらの更新はログ n 時間で償却され、リストの連結は一定です。上記のいくつかのアプローチほど速くはありませんが、プログラムするのは簡単で、たとえば Kruskal の Minimal Spanning Tree Algorithm の Big-O 実行時間を改善するには十分です。