函数具有负值时的大 O 表示法

Question

我需要证明 2n^2 - 2n -7 = O(n^2)，当 n 为 1 或 2 时，我得到 f(n) 的负值。我不确定我证明 Big-O 的方式是否 correct.Your 非常感谢帮助和建议。

              f(n) = 2n^2 - 2n -7 = O(n^2)  if c=2;
              n=1->2(1)^2 - 2(1) -7 = -7 <= 2*(1)^2
              n=2->2(2)^2 - 2(2) -7 = -3 <= 2*(2)^2
              n=3->2(3)^2 - 2(3) -7 = 14 <= 2*(3)^2

Answer 1

Big-Oh 的定义更多地与渐近行为有关，而不是局部行为。如果您的函数随着 n 值的增加而变为负数，比如说它发生振荡，则可能会引起更多关注。但是，对于此函数，没有问题：您可以自由考虑所有大于某些 n0 的值的函数，您可以单独选择。因此，如果函数早期变为负值让您感到困扰，请编写您的证明，以便不使用这些数字。例如：

基本情况：n = 3、f(n) = 2*3*3 - 2*3 - 7 = 18 - 6 - 7 = 5 <= 9 * c = c * 3 * 3 = c * n^2。这是真的，前提是 c >= 5/9.

归纳假设：对于从 3 开始一直到 k 的所有 n，假设 f(n) <= c * n^2。

归纳步骤：我们必须证明f(k+1) <= c * (k+1)^2。我们有 f(k+1) = 2(k+1)^2 - 2(k+1) - 7 = 2k^2+4k+2 - 2k - 2 - 7 = 2k^2 + 2k - 7 < 2k^2 + 4k < 2k^2 + 4k + 2 = 2(k^2 + 2k + 1) = 2(k+1)^2，因此选择 c = 2 在这里有效。

事后看来，很明显 2n^2 - 2n - 7 总是小于 2n^2 正增加 n.

函数具有负值时的大 O 表示法

Big-O notation when the function has negative value

function

big-o

asymptotic-complexity

discrete-mathematics

proof