为什么同一个方程给出不同的大O值

Question

在演讲幻灯片中呈现的一个例子中，大分析让我很困惑。

它指出：2N^2 + 4N = O（N^2）和2N^2 + 4N = O（N^4）

有人能解释中相同的方程如何产生不同的结果？谢谢

Answer 1

首先"="并不意味着它的“等于”，它的意思是“是”在算法分析的意义上。大O的要点是满足这个：

f(x)是O(g(x)) iff 0<=|f(x)|<=c*g(x)其中c是正数。

因此，你的情况2n^2 + 4n = O(n^2) AND 2n^2 + 4n = O(n^4)是真实的。但是，我们总是使用“最佳函数”来描述算法，因此我们使用O(n^2)。

另一方面，f(x)是Ω(h(x)) iff 0<=c*h(x)<=|f(x)|。现在，如果你有h(x)=g(x)，这意味着f(x)是Θ(g(x))