我真的很想知道真正的定義。我試圖讀一本書,但無法理解它。 O:大O符號最壞的情況。 Θ:Theta符號平均情況。
Ω:Ω符號最好的情況。Big-O表示法的定義
爲什麼維基百科只代表Big-O算法的速度,包括其平均,最佳和最差情況?他們怎麼沒有取代那些正式的關鍵字?
我真的很想知道真正的定義。我試圖讀一本書,但無法理解它。 O:大O符號最壞的情況。 Θ:Theta符號平均情況。
Ω:Ω符號最好的情況。Big-O表示法的定義
爲什麼維基百科只代表Big-O算法的速度,包括其平均,最佳和最差情況?他們怎麼沒有取代那些正式的關鍵字?
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)。
我不確定你在哪裏找到這些定義,但我認爲它們是不正確的。
最好的,平均的和最差的情況下,所有功能通常是輸入大小。
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(2n)和a lower bound of Ω(1.5n)並不難,但是〜θ的緊密結合(1.6 n)更難以計算。
大多數人只關心O,因爲它是最常見的最糟糕的情況。 – Cine 2011-01-10 10:47:22
[大O的純英文解釋](http://stackoverflow.com/questions/487258/plain-english-explanation-of-big-o) – royhowie 2014-12-05 04:15:43