algorithm - 大 O 符号（两侧）

Question

我需要一步一步证明：7 + O(n) = O(n)

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

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

标签： algorithm

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. 因此，对于所有n >= N，只要N >= 1 ， g ( n ) = f ( n ) + 7 <= cN + 7 <= ( c + 7) N。

因此，给定常数c和N证明f在 O( n ) 中，常数 ( c + 7) 和 max( N , 1) 用于证明g在 O( n ) 中。QED。