algorithm - 大 O 符号(两侧)

Question

我需要逐步证明:7 + O(n) = O(n)

当两边都有大O的时候，我不知道该怎么做。

我想我理解大 O 符号的概念，但为什么两边都有大 O？

Answer 1

这种表示法的使用不符合大 O 表示法的正式定义，因此不清楚证明需要达到何种形式化程度。此外，由于符号不是正式的，因此需要一些解释来决定实际需要证明的内容。

我将此解释为要求证明，给定 O(n) 中的任何函数，如果将 7 添加到该函数的所有值，则新函数也是在 O(n) 中。更正式地说，对于 O(n) 中的所有 f，函数 g(n) = f(n) + 7 也在 O(n) 中。

这可以从定义中直接证明:

1. 我们需要证明，对于 O(n) 中的每个 f，函数 g(n) = f(n) + 7 也在 O(n) 中。
2. 因为 f 在 O(n) 中，存在常数 c 和 N 这样对于所有n>= N，f的值(n) <= cN .
3. 因此 g(n) = f(n) + 7 <= cN + 7 <= (c + 7)N 对于所有 n>= N，只要 N>= 1。

所以给定常数 c 和 N 证明 f 在 O(n) 中，常数 (< em>c + 7) 和 max(N, 1) 用于证明 g 在 O(n) 中。 QED.