algorithm - ソート時間を変えることによるクラスカルのアルゴリズムの実行時間

Question

私は最小スパニング ツリーの分析を行っていましたが、ソート時間がクラスカルのアルゴリズムの全体的な時間の複雑さにどのように影響するのか疑問に思っていました。

例：

1. 並べ替えができる場合O(n log log n)
2. 並べ替えができる場合O(n)

答えは両方の場合にまだ残っO(e log n)ていますか、それとも変わりますか?

Answer 1

Kruskal アルゴリズムの時間は O(e log e)、エッジを並べ替える時間です。O(e) でそれを行うことができれば、最小スパニング ツリーを見つけるための残りのアルゴリズムが O (e log n) であることを考慮すると、O(e) + O(e log n). それ以降e=O(n^2)、アルゴリズムの時間はO(n^2 log n)またはになりO(e log n)ます。同じ分析でソートに O(e log log e) かかる場合、全体の時間は になりますO(e log log e)。

詳細: 最小全域木を見つける時間は、エッジの並べ替えに必要な時間と、並べ替えられたリストから各エッジを削除して 2 つのばらばらな領域を接続するかどうかを調べるループ (e 回) によって計算されます。(このチェックには O (log n) が必要です)。ループの時間はO(e log n)上記のとおりです。

より洗練された分離集合データ構造を使用して分離領域を見つけてチェックするループは O(E α(V)) 時間で、α は単一値のアッカーマン関数の非常にゆっくりと増加する逆関数です ( WikiPedia ) 。