普利姆算法的总运行时间！

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吗？

- Guestt

Answer 1

一般情况下，我们假设 E 大于 V。因此，忽略低阶项后，得到 E lg V。

- Abdul Samad

Answer 2

具体来说，在有向图中，E 的最大值可以是 V^2。如果我们假设 E = v^2（以考虑最坏情况），那么 E 将包含 V。

- user1114