简化 O((V + E) logV) 时间复杂度

Question

dijkstra算法的时间复杂度为O((V + E) logV)

如果我的图表是 E < V like the image I attached below

我可以去掉 E 并将其简化为 O(VlogV) 吗？

如果可以的话，我想知道为什么E可以忽略？

Answer 1

如果 𝐸 < 𝑉, then the expression 𝑉 + 𝐸 is less than 2𝑉. That coefficient is 不显着 对于大 O 表示法，那么 O((𝑉 + 𝐸) log𝑉) = O(2𝑉log𝑉) = O(𝑉log𝑉)。