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(V ² ))，任何 O(V + E) 的运行时也是 O(V ² )。但这并不意味着说运行时间是 O(V ² )是个好主意，因为这是一个不太精确的界限。在稀疏图中，O(V + E) 是比 O(V ² )更严格的界限。

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

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

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