アルゴリズムの分析のクラスでは、クラスカルのアルゴリズムの次の疑似コードが提示されます。
彼は、ばらばらな集合の森について、次のように述べています。
m 個の MAKE-SET、UNION、および FIND-SET 操作のシーケンス (n は MAKE-SET 操作) は、最悪の場合の時間O(m α (n)) .
ステップ 2 とステップ 5 ～ 8 の複雑さを計算するために使用されます。
接続された G の場合: |E| ≥ |V| -1; m = O(V + E)、n = O(V);
ステップ 2、5 ～ 8: O((V + E) α(V)) = O(E α(V))
α(V) = O(lg V) = O(lg E); O(E lg E) ----- // α(V) はどのように等しいのでしょうか?
Kruskal: ステップ 3、5-8、およびステップ 4: O(E lg E)
観察: |E| < |V|2 -> lg E = O(lg V)
したがって、クラスカルの複雑さ: O(E lg V)
私はこの「alpha(n)」/「α(n)」関数の背後にあるロジックを理解しようとしましたが、私が読んだことから、単純化すると、アッカーマン関数は信じられないほど急速に指数関数的に成長する関数であると思われます。逆は、対数的に信じられないほどゆっくりと成長するものです。
私の解釈が正しければ、「α(n)」は何を表しているのでしょうか? MAKE-SET操作はせいぜいO(lg n)ということですか? 逆アッカーマンの使用はどのように/なぜ必要なのですか? この操作は V 回 (頂点ごとに) 実行されるという印象を受けました。これに続いて、α(V) も O(lg V) = O(lg E) と簡略化されますが、これは、最大で α(V) を O(lg V) で表すことができるということですか?
また、なぜ|E| < |V|^2 -> lg E = O(lg V)ステートメントが作成されましたが、|E| であることはどのようにわかりますか? < |V|^2?
私の質問は本当に要約すると、私の講師が両方とも O(E log V) であると述べたときに、素集合の「森」表現がリンクリストで実装されたものよりも効率的であるように見えるのはなぜですか? したがって、フォレストで互いに素なセットを実装することの難しさが増していることに意味はありますか?