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

Question

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

f(n) 是 O(f(n) + g(n)))

我知道我们可以使用：

f(n) ≤ 常数 * (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)) 吗？

希望这可以帮助！