这里是f(x)=O(g(x))还是反之亦然?

以下所有陈述均属实:

n2       ∈ O(n2)
n2       ∈ O(4n2-2n+2)
4n2-2n+2 ∈ O(4n2-2n+2)
4n2-2n+2 ∈ O(n2)

然而谈论 O(4n 2 -2n+2) 没有多大意义,因为它与 O(n 2 ) ^* ,因此,由于后者更简单,因此没有理由将其称为前者。

^* 对于每个函数 f 因此 ∃N,C: ∀x>N: |f(x)| ≤ C|4n 2 -2n+2| ,这也是事实 ∃N,C: ∀x>N: |f(x)| ≤ C|n 2 | 反之亦然。

关于big-O表示法和类似的问题,需要考虑方程的哪个项 占主导地位 因为n(或x或其他合适的变量名)变得非常大。也就是说,哪个项对方程图的整体形状贡献最大。您应该根据方程式结果绘制哪个项,以获得直线的最接近近似值(近似一对一对应关系)。

关于您的其余问题,它并没有说C>1、我认为C>随着n的增长,2n+2与平方项相比变得很小。

关于为什么它与编码相关:您的代码运行需要多长时间?你能让它跑得更快吗?哪个方程式/代码更有效?您的变量需要多大(即C中的int或long选项)。我想如果有一个“大o”的标签,以前至少有一个关于这个的问题。