Prims算法總計運行時間！

Question

「因此，Prim算法的總時間爲O（V lg V + E lg V）= O（E lg V），這與我們實現Kruskal算法的漸近程度相同。

從http://serverbob.3x.ro/IA/DDU0137.html

但爲什麼是O（V LG V + E LG V）= O（E LG V）？

是因爲E至少是V-1嗎？

Answer 1

因爲在正常情況下，我們假設E是通過忽略，我們得到ËLG V低階項比V.大所以

Answer 2

具體而言，E可以在有向圖是一個最大的V^2。如果我們假設E = v^2（考慮到最壞的情況），E吞下V.