algorithm - E が v を支配するのはなぜですか?

Question

Kruskal アルゴリズムの実行時間を分析したところ、O(ElogE+Elogv+v) が得られました。

私は教授に尋ねたところ、グラフが非常にまばらで、多くの孤立した頂点がある場合、V が E を支配し、そうでない場合は E が V を支配し、その理由が理解できないと彼は言いました。グラフがまばらではないが、それでも V が E より大きい例を挙げることができます

この混乱を解消するのを手伝ってくれる人はいますか?

Answer 1

密度 = エッジの数 / 可能なエッジの数 = E / (V(V-1))/2

グラフを木にします E = V - 1

したがって、V = (E + 1)

そしてクルスカルの複雑さは

O(E log E + E log V + V) = O(E log E + E log (E + 1) + (E + 1)) = O( E log E )

だからEが優勢。E = O(V) である限り、E が支配的です。