algorithm - 显示 f(n) = O(f(n) + g(n))？

Question

我想知道以下 Big-O 比较的证明是什么:

f(n) is O(f(n) + g(n)))

我知道我们可以使用:

f(n) ≤ constant * (f(n) + g(n))

但是不知道怎么跟进。

如果我们用 big-Ω 替换 big-O 呢？

Answer 1

如果您知道函数 g(n) 是非负的，那么请注意

f(n) ≤ f(n) + g(n) = 1 · (f(n) + g(n))

鉴于此，您能否使用大 O 表示法的正式定义来证明 f(n) = O(f(n) + g(n))？

如果 g(n) 不一定非负，则此结果不一定为真。例如，取 f(n) = n 和 g(n) = -n。则 f(n) + g(n) = 0，f(n) = O(0) 不成立。

至于 Ω 的情况，你确定这个结果一定是真的吗？作为提示，尝试选择 f(n) = n 和 g(n) = 2ⁿ。这里的 f(n) 真的是 Ω(f(n) + g(n)) 吗？

希望这对您有所帮助!