ユニオン検索アルゴリズムの時間の複雑さを分析するための簡潔で簡単なアプローチを教えてください。2 つのケースで 1. 標準的なアプローチ 2. 加重和集合ヒューリスティック アプローチ
標準バージョンでは、その時間の複雑さはO(n^2) であり、重み付きユニオン ヒューリスティック アプローチの場合はO(m + n logn) です。
しかし、私はそれがどのように来ているのかわかりません。仮定: n 個の要素とリンクされたリストのデータ構造があり、各ノードがリストの先頭を指している、m=make set 操作があるとします。
まずいくつかの定義: mは make-set 操作の数です。nは、union/find 操作の合計です。
標準版
join(a,b)それがbのルートになると仮定しますa。
、 のように0.5n 回の呼び出しシーケンスがある場合、ボタン内で0.5nノードのチェーンを作成できます。次に、 0.5n時間がかかるため、 0.5n回呼び出すと、ランタイムは0.25n^2=O(n^2)になります。joint(1,2)joint(2,3)joint(3,4)1find(1)
m 回の操作を行う必要があるmakesetため、最終的には O(m+n^2) になります。
加重組合
重量はセットのサイズ (ランクではなく) であると想定しています。
与えられた集合に対して、それを表す木の高さをhとし、そのサイズをwとします。は、そのセットfindで最大h時間かかります。帰納法により、 h<=log(w)であることを証明できます。
w=1とh=0を持つ単一のノードの場合、式は自明に成り立ちます。
ここで、 aが新しいルートになる2 つのツリーaとbの間の結合を考えます。h<=log(w)がaとbに当てはまると仮定すると、和集合にも当てはまることを示します。wa>=wb => wab = wa+wb >= 2wbであることはわかっています。aが厳密にbよりも高い場合、 hab = ha <= log(wa) <= log(wab)となります。それ以外の場合 ( hb >= ha の場合)、 hab = 1+hb <= 1+log(wb) = log(2wb) <= log(wab) となります。
これは、 h<=log(w)が成り立つことを証明しています。より少ない数学用語で言えば、任意のセットの高さがそのサイズの対数よりも小さいことを証明したため、検索には最大でO(log(k))時間かかります。ここで、k はセットのサイズです。
jを共用体操作の数とします。それぞれunionが 2 つの要素に接触するため、任意のセットの最大サイズは2jによって制限されます。
したがって、ユニオンと検索の実行時間はO(j+k log(2j)) = O(n + n log(2n)) = O(n log(n))です。ここでもm sを実行する必要があるmakesetため、合計でO(m + n log(n))が得られます。