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.