algorithm - クラスカルアルゴリズムの時間複雑性?

Question

このようなクラスカルアルゴリズムの時間計算量を計算しています（添付の画像のアルゴリズムを参照してください）

T(n) = O(1) + O(V) + O(E log E) + O(V log V)
     = O(E log E) + O(V log V)
as |E| >= |V| - 1
T(n) = E log E + E log E
     = E log E

CLRS アルゴリズム:

それは正しいですか、それとも何か間違ったことをしていますか教えてください。

Answer 1

クラスカルは O(E log E); あなたの導出は正しいです。E <= V * V であるため、O(E log V) とも言えます。したがって、log(E) <= 2 log(V) (なぜそれを覚えているのかわかりませんが、それ以外は、教授がある時点で試験に...）

Answer 2

|V|以来 > |E|+1 の場合、E 項の代わりに V 項を使用したタイトな上限を優先します。

    |E| <= |V|²   
.   log |E| < log |V|²   
.   log |E| < 2 log |V| 
.   running time of MST-KRUSKAL is: O(E log V)

Answer 3

返事が遅れて申し訳ありません。
Kruskal アルゴリズムのランタイムは O(E log E) であり、O(E log V) ではありません。

エッジを最初にソートする必要があり、考慮しているエッジが安全なエッジであるかどうかを検証するためのランタイムを支配する O(E log E) が必要であり、これには O( E log V) が必要です。そして |E| > |V|((グラフがすでにツリーである場合のコーナーケース))、したがって、ランタイムが O(E log E) であると想定しても安全です。

Answer 4

5 行目から 9 行目までの複雑さは O(E) です。

5. O(E)
6. O(1)
7. O(1)
8. O(1)
9. O(1)

5行目までは、複雑さを正しく計算しています。最後に、ここでの支配要因は O(E lg E) です。したがって、複雑さは O(E lg E) です。