algorithm - 在这种情况下，我对 big o 的解释是否正确？

Question

我正试图向我的 friend 解释为什么 7n - 2 = O(N)。我想根据大 O 的定义这样做。

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

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

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

在这种情况下，下列解释是否正确？

• 7n - 2 <= C 。 n

• -2 <= C 。 n - 7n

• -2 <= n (C - 7)

• -2/(C - 7) <= 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 以查看对于所有 n ≥ n 的 7n - 2 ≤ cn ₀。

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

7n + 2

≤ 7n + 2n (for all n ≥ 1)

= 9n

所以通过检查我们可以选择 c = 9 和 n₀ = 1 并且我们有 7n + 2 ≤ cn 对于所有 n ≥ n₀，所以 7n + 2 = O(n)。

请注意，在这个数学中，我们在任何时候都没有假设最终的不平等，这意味着我们永远不必冒被零除错误的风险。