algorithm - 广度优先搜索完全图的复杂度是多少？

Question

据说 BFS 的复杂度是线性的，即 O(V+E)，但有向完全图中边的总数是 V*(V-1)，这是大小的 2 次函数图。那么 BFS 是否需要 O(V^2) 时间来遍历一个完整的图？

Answer 1

是的，我假设您已经计算过了。

O(V+E) = O(V + V*(V-1))
       = O(V + V*V - V)
       = O(V*V)