1

Kruskal のアルゴリズムが BFS を使用して実装され、サイクルを作成してエッジを追加するかどうかを確認した場合、アルゴリズムの全体的な Big-O 実行時間はどのくらいになりますか?

4

1 に答える 1

4

だろうO(V * E + E * log E)。ツリーにはエッジがあり (ツリーがまだ完全に構築されていない場合はそれ以下)、各エッジ (は頂点の数、はエッジの数) に対して実行されるため、各 BFS にはO(V)時間がかかります。だから合計です。用語はエッジのソートに由来します。V - 1VEO(V * E)E * log E

于 2014-11-19T09:43:10.030 に答える