真或假 -> O(m+n) = O(m)

Question

让

假设图 G(V,E) 是无向且连通的。

我所做的是将 m 替换为 (n*(n-1)/2)，因为这是节点数方面的最大可能边。

所以，我发现这是真的，

但是，真正的答案是错误的。

谁能从概念上解释一下与 Big-Oh 复杂性进行比较意味着什么？

Answer 1

你的想法对我来说似乎是正确的，只有一个例外。你能确定两个相同的顶点之间不能有两条或更多条边吗？所以图不是multi-graph？否则 m = X * (n*(n-1))/2 其中 X 可以增长到无穷大，它是问题中的一个新变量。那么复杂度将类似于 O(X*n*n).

无论如何，方程仍然是正确的，因为第一个子句中的 +n 仍然可以省略（因为二次函数 "overcharges" 是线性的）。

Answer 2

边数 m 以

为界是正确的

m <= (n*(n-1)/2)

和

n*(n-1)/2 = (n^2-n)/2

这意味着问题中的推理产生

m+n <= (n^2-n)/1+n = O(n^2)

与O(m)的复杂度相同；然而，以明确考虑边数和节点数的方式说明算法的复杂性比使用 (n^2-n)/2.

的最坏情况界限更精确

Answer 3

答案：正确

图是连通的 => m >= n-1 => m = n-1+k 其中 k >= 0.

但是 m <= n(n-1)/2 因为如果每 2 个节点之间有一条边，则不需要更多边。 => n-1+k <= n(n-1)/2 => k <= (n-1)(n/2-1) => k <= (n-1)(n-2)/2.

所以，我们有 m = n - 1 + k 其中 0 <= k <= (n-1)(n-2)/2 ； k表示超过连接所需的最小边数的边数。

O(m+n) = O(n-1+k+n) = O(2n-1+k) = O(2n+k) = a

O(m) = O(n-1+k) = O(n+k) = b

现在，让我们来看 3 种情况：

lim(n->inf) n/k = 0

a = O(k(2n/k + 1)) = O(k)

b = O(k(n/k + 1)) = O(k)
lim(n->inf) n/k = constant

a = O(2*constant*k + k) = O(another_constant * k) = O(k)

b = O(constant*k + k) = O(another_constant2 * k) = O(k)
lim(n->inf) n/k = inf => lim(n->inf) k/n = 0

a = O(n(2 + k/n)) = O(2n) = O(n)

b = O(n(1 + k/n)) = O(n)

所以，在任何情况下都是如此。

True or False -> O(m+n) = O(m)