algorithm - 大O标记(两面)

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

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

我想我了解大O表示法的概念，但是为什么双方都有大O？

最佳答案

这是大O符号的形式定义:
f(n) = O(g(n)) means there are positive constants c and k, such that 0 ≤ f(n) ≤ cg(n) for all n ≥ k. The values of c and k must be fixed for the function f and must not depend on n.(big-O notation)。



例如，如果您的复杂度是O(n^2)，那么您可以保证存在某个n值(大于k)，之后f(n)在任何情况下都不会超过c g(n)。

让我们尝试证明q(n) = f(n) + 7是O(n)，其中f(n)是O(n):

根据定义，存在一个函数f(n)，以便所有f(n) ≤ c n的n ≥ k。

现在，我们要证明q(n)是O(n)。我们通过矛盾证明了这一点。我们说如果q(n)不是O(n)，则不存在k'和c'，因此所有q(n) ≤ c' n (原始假设)的n ≥ k'都不存在。现在，

所有q(n) = f(n) + 7 ≤ c n + 7的n ≥ k ----(1)。

根据定义，c > 0和k > 0。现在，所有(c + 1) n ≥ c n + 7，n ≥ max(k, 7)的c > 0
=>所有(c + 1) n ≥ f(n) + 7和n ≥ max(k, 7)的c > 0(来自eqn(1))

=>所有(c + 1) n ≥ q(n)的n ≥ max(k, 7)，c > 0 ----(2)

用上述方程式替换c' = c + 1和k' = max(k, 7)，我们很快发现了一个矛盾:

所有c' n ≥ q(n)的n ≥ k'(在步骤2中写为原始假设)

这是一个矛盾，因为违反了我们最初的假设，即不存在c'和k'这样的值。因此，O(n) + 7是O(n)。

这就完成了您的证明。希望能帮助到你!

编辑:足以表明存在一些k'和c'足以使我们的证明起作用。我们可以简单地跳过矛盾部分。

关于algorithm - 大O标记(两面)，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/58860094/