time-complexity - O(V+E) 等价于 O(V^2) 吗？

Question

我的问题是关于是否O(V+E) = O(V^2) .

基本上，如果 O(V+E)是线性时间使得 V+E = n ，不会O(V^2)也是线性时间？

我假设 O(V+E) 的最坏情况/上限是每个顶点之间的边，这将导致 (V-1)^2边缘。我还认为可以考虑 V^2 ，所以我认为这相当于 O(V^2) .

Answer 1

由于您阐明的原因 (E = O(V2))，任何 O(V + E) 的运行时也是 O(V2)。但这并不意味着说运行时间是 O(V2) 是个好主意，因为这是一个不太精确的界限。在稀疏图中，O(V + E) 是比 O(V2) 更严格的界限。

然而，反过来说是不正确的。例如，考虑这个算法:

for each node v in V:
   for each node u in V:
       print (v, u)

该算法的运行时间为 Θ(V2)，其运行时间不依赖于图中边的数量。因此，说运行时间为 O(V + E) 是不正确的，因为在边数较少的图中(比如一棵树)，O(V + E) 的边界会错误地预测运行时间与节点数量呈线性关系，而 O(V2) 的运行时间将正确地将运行时间设置为二次方的上限。