complexity-theory - 我们可以说 2x+1 = o(-5x^2+2)

little-o 渐近符号的定义是“f(x) 是 ο(g(x))，如果对于任何常数 c > 0，存在一个 n0 使得 0 ≤ f(n) < c*g(n) 。”

通过这个定义，我们知道，对于任何 n > 1，x 的任何线性函数都是 o(x^2) 和 o(x^n)。

我们也可以说 f(x) = 2x + 1 是 o(-5x^2 +2)，因为对于一些接近 0 的 x 值，(2x+1)<(-5cx^2 +2)，其中 c 是任何正常数？

如果上述问题的答案是肯定的，那么，我得到的另一个问题 -

假设 g1(x) = (-5x^2 + 2)，g2(x) = -5x^2。这里 g1(x) 和 g2(x) 具有相同的顺序。令 f(x) = (2x+1)。因为 f(x) = o(g1(x))，所以 f(x) = o(g2(x))??

如果这也是正确的，那么我在上面添加的图表显示对于所有 x 值 g2(x) < f(x)。所以f(x)不是g2(x)，这是矛盾的！！

如果 f(x) = o(g2(x))，那么 little-o 的定义必须修改为 |f(x)| 和 |g(x)| 代替 f(x) 和 g(x)。

“f(x) 是 ο(g(x))，如果对于任何常数 c > 0，存在一个 n0 使得 0 ≤ |f(n)| < c*|g(n)|。”

请让我知道你的想法。

标签： complexity-theory

实际上，您的定义并不完整，因为我们几乎没有：

定义：设 f(n) 和 g(n) 是将正整数映射到正实数的函数。如果对于任何实常数 c > 0，存在一个整数常数 n0 ≥ 1 使得 0 ≤ f(n) < c*g(n); 对于所有大于 n0 的 n。