Big-O表示法的定義

Question

我真的很想知道真正的定義。我試圖讀一本書，但無法理解它。 O：大O符號最壞的情況。 Θ：Theta符號平均情況。
Ω：Ω符號最好的情況。

爲什麼維基百科只代表Big-O算法的速度，包括其平均，最佳和最差情況？他們怎麼沒有取代那些正式的關鍵字？

Answer 1

O，Θ和Ω不代表最差，平均和最好的情況;儘管它們有相似的含義。 （n）= O（g（n））意味着對於大的n值，f的增長慢於g（「n> n 」意思是「對於n的大數值」上下文）。這並不意味着g是最糟糕的情況：g可能比最壞的情況更差（例如，快速排序是也是 O（n！））。對於更復雜的算法，目前正在進行研究以確定最小的Big-O的實際複雜度：原始作者主要發現Big-O上限。

Ω符號意味着反向（f增長快於g），這意味着它可能比最好的情況更好（例如所有算法都是Ω（1））。

有許多算法沒有單個函數g，使得複雜度既是O（g）又是Ω（g）。例如，插入排序具有O（n2）的Big-O下界（意思是你找不到小於n2的任何東西）和Ω（n）的Ω上界。

其他算法做到：合併排序既是O（n log n）又是Ω（n log n）。發生這種情況時，它被寫爲Θ（n log n），這意味着並非所有算法都具有Θ-符號複雜性（並且值得注意的是，具有最壞情況或最好情況下的算法沒有一個）。

爲了消除可能性極低的最壞情況，檢查平均情況的複雜性 - 在左側用標準的「f」值替換一個不同的函數「f _avg」只考慮最可能的結果。所以，對於快速排序，f = O（n²）是最好的，但可以得到，但f _avg = O（n log n）。

Answer 2

我不確定你在哪裏找到這些定義，但我認爲它們是不正確的。

最好的，平均的和最差的情況下，所有功能通常是輸入大小。

Big-O，Theta和Omega分別表示任何給定函數的上限，下限和下限。

也就是說最好的情況有一個大的O，Theta和Omega界。平均情況和最壞情況也是如此。

參見：How do O and Ω relate to worst and best case?

注：大O通常是（可以說是不正確的），用來指示緊約束（而不是西塔）一個。

---

讓我們來考慮一下插入排序的例子。

最好的情況是當它已經排序，在這種情況下，它會花費線性時間，即f(n) = k1n時間爲一些常數k1。 （n），Θ（n），Ω（n），其中O（n）是0（n）。根據定義，我們也可以說它是O（n ），O（n ），...或Ω（1），Ω（log n），Ω（log log n），...。但是它通常預期會呈現最緊密的界限。

最壞和平均情況是g(n) = k2n2和h(n) = k3n2，這兩者都是爲O（n 2 ），Θ（N ），Ω（N ）。

---

現在你可能會說：這不是很有用，爲什麼我們需要三個邊界，如果它們總是相同的？我們爲什麼不到處使用Theta？一般來說，你是絕對正確的 - 算法通常只用一個界限（通常是緊密界限）來描述。

但是，對於一些算法，很難確切地確定緊密邊界是什麼，而很容易獲得上限和/或下限。計算Fibonacci numbers的未優化算法就是一個這樣的例子 - 找到an upper bound of O(2ⁿ)和a lower bound of Ω(1.5ⁿ)並不難，但是〜θ的緊密結合（1.6 ⁿ）更難以計算。