math - Prims Algorithm 総実行時間!

Question

「したがって、プリムのアルゴリズムの合計時間は O(V lg V + E lg V) = O(E lg V) であり、これはクラスカルのアルゴリズムの実装と漸近的に同じです。」

http://serverbob.3x.ro/IA/DDU0137.htmlより

しかし、なぜ O(V lg V + E lg V) = O(E lg V) なのですか??

E が少なくとも V-1 だからですか?

Answer 1

通常、E は V よりも大きいと想定されるため、低次の項を無視することで、E lg V が得られます。

Answer 2

具体的には、Eは有向グラフで最大V^2になる可能性があります。E = v ^ 2（最悪の場合を説明するため）と仮定すると、EはVを飲み込みます。