Warm tip: This article is reproduced from serverfault.com, please click
complexity theory-我们可以说2x + 1 = o（-5x ^ 2 + 2）
(complexity theory - Can we say 2x+1 = o(-5x^2+2))
发布于 2020-12-08 06:52:56
小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），因为对于x接近0的某些值，（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）|。”
请让我知道你的想法。
Questioner
Monalisha Bhowmik
Viewed
0
如果定义中应同时包含f和g的正整数到正实数的映射，则可以。但是，在给出的此链接中，未提及肯定。在某个地方给出了，在其他地方没有给出，这令人困惑。g（n）不能为正输入取负值吗？
我想，这将是一个有思想的假设，因为所有这些定义都是针对复杂性理论定义的，而复杂性理论针对的是算法运行时，而负运行时根本就没有意义。用数学的眼光看，函数的所有上限可以是一点点o，按照惯例，Big O表示在函数的最低上限（对于大于n0的数）。
同样对于小o，我们必须具有：对于常数k> 0的每个选择，您都可以找到一个常数a，使得不等式0 <= f（x）<kg（x）对于所有x> a成立。对于在0附近的相对较小的k不会发生这种情况，因此f不是o（g）