大哦 - 为什么这种不平等是真的？

Question

我正在阅读Skiena的"算法设计手册".

第一章阐述了Big O符号的正式定义:

f(n) = O(g(n))意味着c * g(n)是上限f(n).即,存在一些常数c,对于足够大的n ,f(n)总是小于或等于c * g(n).(即n >= n0某些常数n0)

这很好,也很有意义.

但后来作者继续描述特定功能的大O: 3n^2 - 100n + 6

他说这O(3n^2 - 100n - 6)不等于O(n).而他的理由是,对于c我选择的任何一个,c * n总是< 3n^2何时n>c.这是真的,但那(-100n + 6)部分呢？

让我们说我选择c = 1和n = 2. 3n^2 - 100n + 6 = 12 - 200 + 6 = -182

和c * n是1*2这是2.-182肯定不到2,为什么Skiena会忽略这些条款呢？

Answer 1

请注意n >= n0定义中的内容.

如果您选择了一些c和n0,它必须是真正的每个 n > = n0,而不仅仅是n0.

所以,如果你有,c = 1并且n0 = 2它也必须是真实的n = 1000,例如,它不是.

3n^2 - 100n + 6
=> 3(1000)^2 - 100(1000) + 6 = 3 000 000 - 100 000 + 6 = 2 900 006

c.n
=> 1(1000) = 1 000