algorithm - 在 big-O 中使用 < 或 ≤

Question

我已经看到了 O 表示法的两种不同的正式定义：

f(n) = O(g(n)) 如果有常数 n ₀ , c 其中对于任何 n ₀，我们有 f(n) < cg(n)

和

f(n) O(g(n)) 如果有常数 n ₀ , c 其中对于任何₀，我们有 f(n) ≤ cg(n)

区别在于 f(n) 是严格小于 cg(n) 还是小于或等于 cg(n)。

这些定义是否相等？如果是这样，我该如何证明？

Answer 1

首先，如果你有

f(n) < cg(n) 对于任何 n ≥ n ₀

那么情况也是如此

f(n) ≤ cg(n) 对于任何 n ≥ n ₀。

同样，假设

f(n) ≤ cg(n) 对于任何 n ≥ n ₀

假设 g(n) ≥ 1，那么你得到，对于任何 n ≥ n ₀，

f(n) ≤ cg(n) ≥ cg(n) + 1 ≤ cg(n) + g(n) = (c + 1)g(n)

因此，使用新常数 c' = c + 1，我们得到

f(n) < c' g(n) 对于任何 n ≥ n ₀

希望这可以帮助！