在这种情况下，我对big o的解释正确吗?

Question

我正试图向我的朋友解释为什么7n - 2 = 0 (N)。我想根据大o的定义来做。

根据大O的定义，f(n) = O(g(n)) if:

我们可以找到实值C和整数值n0>= 1使得:

• f(n)<= C。对于n>= n0的所有值G (n)

在这种情况下，下面的解释正确吗?

• 7n <= C。n

• -2 <= C。n - 7n

• 2 & lt; = n ( C - 7)

• 2/( C - 7) & lt; = n

如果我们考虑C = 7，数学上，-2/(C - 7)等于负无穷，所以

• n>=(负无穷)

这意味着对于n>=(负无穷)的所有值以下成立:

• 7n - 2 <= 7n

现在我们必须选择n0，这样对于所有n>= n0和n0>= 1都成立:

• 7n - 2 <= 7n

由于对于n>=(负无穷)的所有值不等式成立，我们可以简单地取n0 = 1

Answer 1

你做对了。但是，从根本上说，您使用的逻辑不起作用。如果你试图证明存在n₀和c使得f(n) &;Cg (n)对于所有n ≥N ₀，那么你就不能假设f(N) ≤Cg (n)因为这是你最终要证明的!

相反，看看是否可以从初始表达式(7n - 2)开始，并将其按摩成以cn为上限的值。这里有一种方法:因为7n - 2 ≤7n，我们可以(通过检查)取n₀ = 0和c = 7来得到7n - 2 ≤Cn代表所有n ≥n <子> 0 。

对于一个更有趣的情况，让我们用7n + 2试试:

7n + 2

勒;7n + 2n(对所有n ≥1)

= 9 n

我们可以选择c = 9 n₀ = 1得到7n + 2 ≤Cn代表所有n ≥n₀，所以7n + 2 = 0 (n)

请注意，在这个数学过程中，我们没有假设最终不等式，这意味着我们不必冒被0除的错误的风险。