大O和函數統治

Question

我目前正在從我的教科書，關於Big-O符號以及函數如何互相支配一些問題。

這些是我從我的書看的功能。

1. n²

2. n² + 1000n

3. n（如果n爲奇數）
   n³（如果n是偶數）

4. n（如果n ≤ 100） n³（如果n > 100）

我試圖找出哪些函數＃1佔據主導地位。我知道＃1和＃2簡化爲n²，所以它不支配＃2。但是，分割函數（＃3和＃4）給我帶來了問題。 ＃1僅在一定條件下支配函數，而在另一種條件下，＃1被另一函數支配。那麼這是否意味着，既然它並不總是支配它，那它從技術上來說並不算是統治它呢？函數＃1是否不支配這些函數中的任何一個，或者它是否支配所有奇數的＃3，以及所有數字≤100的支持＃4？我看到的方式是，＃1不支配＃2，只支配奇數的＃3，只支配＃4的數字≤100.我在正確的軌道上？

感謝任何人都可以提供的幫助。我正在艱難地嘗試向我自己解釋這一點。

Answer 1

我不確定什麼「主宰」意味着你的情況。可以說「f(n)占主導地位g(n)」翻譯爲f(n) ∈ O(g(n))，其中O(g(n))是最差的情況下的複雜性。

所以我們應該首先計算最壞情況下的複雜性：

• n²是Θ(n²)
• n² + 1000n也是Θ(n²)
• n（如果n爲奇數）n³（如果n爲偶數）是在Θ(n³)（只挑選最差的情況出現在所有案例的50％中，用於隨機選擇n）
• n（如果n ≤ 100）n³（如果n > 100）也在Θ(n³)之內，因爲Big-O依賴於漸近（大值爲n）。

現在我們可以比較最壞的情況下的複雜性，並看到＃1僅支配＃2。

也許你想把最壞情況下的複雜度改變爲平均情況。但只有＃3纔會有變化。 經過計算(n³ + n)/2我們注意到，即使是＃3的平均情況在Θ(n³)。

如果你看最好的情況，你會得到第一個改變，但也只能用於＃3。這裏最好的情況是Θ(n)，所以這裏是排名第一的＃3。

注意，＃4的最好的情況是不Θ(n)，因爲複雜性只爲n → ∞成立，所以我們忽略的n < c₀所有情況下c₀是一個常數。