O、Θ、Ω、o、ω,別再傻傻分不清了!
關(guān)注公眾號(hào)“彤哥讀源碼”，解鎖更多源碼、基礎(chǔ)、架構(gòu)知識(shí)！
你好，我是彤哥，一個(gè)每天爬二十六層樓還不忘讀源碼的硬核男人。
前面幾節(jié)，我們一起學(xué)習(xí)了算法的復(fù)雜度如何分析，并從最壞、平均、最好以及不能使用最壞情況全方位無死角的剖析了算法的復(fù)雜度，在我們表示復(fù)雜度的時(shí)候，通常使用大O來表示。
但是，在其他書籍中，你可能還見過Θ、Ω、o、ω等符號(hào)。
那么，這些符號(hào)又是什么意思呢？
本節(jié)，我們就來解決這個(gè)問題。
讀音我們先來糾正一波讀音：
O，/??/，大Oh
o，/??/，小oh
Θ，/?θi?t?/，theta
Ω，/o??meɡ?/，大Omega
ω，/o??meɡ?/，小omega
是不是跟老師教得不太一樣^^
數(shù)學(xué)解釋Θ
Θ定義了一種精確的漸近行為（exact asymptotic behavior），怎么說呢？
用函數(shù)來表示：
對(duì)于f(n)，存在正數(shù)n0、c1、c2，使得當(dāng) n>=n0 時(shí)，始終存在 0 <= c1*g(n) <= f(n) <= c2*g(n)，則我們可以用 f(n)=Θ(g(n))表示。
用圖來表示：
Θ同時(shí)定義了上界和下界，f(n)位于上界和下界之間，且包含等號(hào)。
比如說，f(n) = 2n^2+3n+1 = Θ(n^2)，此時(shí)，g(n)就是用f(n)去掉低階項(xiàng)和常數(shù)項(xiàng)得來的，因?yàn)榭隙ù嬖谀硞€(gè)正數(shù)n0、c1、c2，使得 0 <= c1*n^2 <= 2n^2+3n+1 <= c2*n^2，當(dāng)然，你說g(n)是2*n^2也沒問題，所以，g(n)實(shí)際上滿足這個(gè)條件的一組函數(shù)。
好了，如果Θ你能理解了，下面四個(gè)就好理解了。
O
O定義了算法的上界。
用函數(shù)來表示：
對(duì)于f(n)，存在正數(shù)n0、c，使得當(dāng) n>=n0 時(shí)，始終存在 0 <= f(n) <= c*g(n)，則我們可以用 f(n)=O(g(n))表示。
用圖來表示：
O只定義上界，只要f(n)不大于c*g(n)，就可以說 f(n)=O(g(n))。
比如說，對(duì)于插入排序，我們說它的時(shí)間復(fù)雜度是O(n^2)，但是，如果用Θ來表示，則必須分成兩條：
最壞的情況下，它的時(shí)間復(fù)雜度為Θ(n^2)；
最好的情況下，它的時(shí)間復(fù)雜度為Θ(n)。
這里的n^2只是g(n)這一組函數(shù)中最小的上界，當(dāng)然，g(n)也可以等于n^3。
不過，我們一般說復(fù)雜度都是指的最小的上界，比如，這里插入排序的時(shí)間復(fù)雜度如果說是O(n^3)，從理論上來說，也沒問題，只是不符合約定罷了。
插入排序最好的情況就是數(shù)組本身就是有序的。
o
o定義的也是算法的上界，不過它不包含等于，是一種不精確的上界，或者稱作松上界（某些書籍翻譯為非緊上界）。
用函數(shù)來表示：
對(duì)于f(n)，存在正數(shù)n0、c，使得當(dāng) n>n0 時(shí)，始終存在 0 <= f(n) < c*g(n)，則我們可以用 f(n)=o(g(n))表示。
用圖來表示：
o表示僅僅是大O去掉等于的情況，其他行為與大O一模一樣。
Ω
Ω定義了算法的下界，與O正好相反。
用函數(shù)來表示：
對(duì)于f(n)，存在正數(shù)n0、c，使得當(dāng) n>=n0 時(shí)，始終存在 0 <= c*g(n) <= f(n)，則我們可以用 f(n)=Ω(g(n))表示。
用圖來表示：
Ω只定義下界，只要f(n)不小于c*g(n)，就可以說 f(n)=Ω(g(n))。
比如，對(duì)于插入排序，我們可以說它的時(shí)間復(fù)雜度為Ω(n)，不過，這通常沒有什么意義，因?yàn)椴迦肱判蛟谧詈玫那闆r下很少，基本都是在最壞情況或者平均情況。
ω
ω同樣定義的是下界，只不過不包含等于，是一種不精確的下界，或者稱作松下界（某些書籍翻譯為非緊下界）。
用函數(shù)來表示：
對(duì)于f(n)，存在正數(shù)n0、c，使得當(dāng) n>n0 時(shí)，始終存在 0 <= c*g(n) < f(n)，則我們可以用 f(n)=ω(g(n))表示。
用圖來表示：
ω表示僅僅是大Ω去掉等于的情況，其他行為與大Ω一模一樣。
通俗理解| 符號(hào) | 含義 | 通俗理解 |
|---|---|---|
| Θ | 精確的漸近行為 | 相當(dāng)于“=” |
| O | 上界 | 相當(dāng)于“<=” |
| o | 松上界 | 相當(dāng)于“<” |
| Ω | 下界 | 相當(dāng)于“>=” |
| ω | 松下界 | 相當(dāng)于“>” |
為了幫助同學(xué)們快速查閱英文資料，彤哥特地把這幾節(jié)涉及到的英語(yǔ)單詞匯總了一下：
| 漢語(yǔ) | 英文 |
|---|---|
| 復(fù)雜度 | complexity |
| 時(shí)間復(fù)雜度 | time complexity |
| 空間復(fù)雜度 | space complexity |
| 漸近分析 | asymptotic analysis |
| 最壞情況 | the worst case |
| 最好情況 | the best case |
| 平均情況 | the average case |
| 精確的漸近行為 | exact asymptotic behavior |
| 低階項(xiàng) | low order terms |
| 常數(shù)項(xiàng)（前置常數(shù)） | leading constants |
| 松上界 | loose upper-bound |
本節(jié)，我們分別從讀音、數(shù)學(xué)、通俗理解等三個(gè)方面闡述了Θ、O、o、Ω、ω的含義，并在最后給出了這幾節(jié)涉及到的術(shù)語(yǔ)對(duì)應(yīng)的英文，有了這些英文，你也可以快速地查閱這方面的資料。
不過，在我們平時(shí)與人交流的過程中，大家還是習(xí)慣于使用大O表示法，一來它表示最壞情況，最壞情況通常可以直接代表算法的復(fù)雜度，二來它比較好書寫。
所以，我們只需要記住大O就可以了，只不過在別人提到Θ、Ω、ω我們知道是什么含義就可以了。
前面幾節(jié)講了這么多，其實(shí)，還是只涉及了很簡(jiǎn)單的算法復(fù)雜度。
那么，常見的算法復(fù)雜度有哪些呢？
下一節(jié)，我們接著聊。