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

Question

我正在阅读 Skiena 的《算法设计手册》。

第一章阐述了大 O 表示法的正式定义:

f(n) = O(g(n)) 表示 c * g(n) 是 f(n)< 的上限。即存在一些常量 c 使得 f(n) 对于足够大的 n 总是小于或等于 c * g(n) . (即 n >= n0 对于某个常量 n0)

所以这很好并且有道理。

但随后作者继续描述了特定函数的大 O:3n^2 - 100n + 6

他说 O(3n^2 - 100n - 6) 不等于 O(n)。他的理由是，对于我选择的任何 c，当 n>c< 时，c * n 总是 <3n^2/。这是真的，但是 (-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，它必须对 each 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