爲什麼同一個方程給出不同的大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))