O、Θ、Ω、o、ω，別再傻傻分不清了！

• 2020 年 7 月 23 日
• 筆記
• B+樹, 二叉樹, 堆, 數據結構, 數組, 棧, 演算法, 紅黑樹, 鏈表, 隊列

前言

本篇文章收錄於專輯：//dwz.win/HjK，點擊解鎖更多數據結構與演算法的知識。

你好，我是彤哥，一個每天爬二十六層樓還不忘讀源碼的硬核男人。

前面幾節，我們一起學習了演算法的複雜度如何分析，並從最壞、平均、最好以及不能使用最壞情況全方位無死角的剖析了演算法的複雜度，在我們表示複雜度的時候，通常使用大O來表示。

但是，在其他書籍中，你可能還見過Θ、Ω、o、ω等符號。

那麼，這些符號又是什麼意思呢？

本節，我們就來解決這個問題。

讀音

我們先來糾正一波讀音：

• O，/əʊ/，大Oh
• o，/əʊ/，小oh
• Θ，/ˈθiːtə/，theta
• Ω，/oʊˈmeɡə/，大Omega
• ω，/oʊˈmeɡə/，小omega

是不是跟老師教得不太一樣^^

數學解釋

Θ

Θ定義了一種精確的漸近行為（exact asymptotic behavior），怎麼說呢？

用函數來表示：

對於f(n)，存在正數n0、c1、c2，使得當 n>=n0 時，始終存在 0 <= c1*g(n) <= f(n) <= c2*g(n)，則我們可以用 f(n)=Θ(g(n))表示。

用圖來表示：

Θ同時定義了上界和下界，f(n)位於上界和下界之間，且包含等號。

比如說，f(n) = 2n^2+3n+1 = Θ(n^2)，此時，g(n)就是用f(n)去掉低階項和常數項得來的，因為肯定存在某個正數n0、c1、c2，使得 0 <= c1*n^2 <= 2n^2+3n+1 <= c2*n^{2，當然，你說g(n)是2*n}2也沒問題，所以，g(n)實際上滿足這個條件的一組函數。

好了，如果Θ你能理解了，下面四個就好理解了。

O

O定義了演算法的上界。

用函數來表示：

對於f(n)，存在正數n0、c，使得當 n>=n0 時，始終存在 0 <= f(n) <= c*g(n)，則我們可以用 f(n)=O(g(n))表示。

用圖來表示：

O只定義上界，只要f(n)不大於c*g(n)，就可以說 f(n)=O(g(n))。

比如說，對於插入排序，我們說它的時間複雜度是O(n^2)，但是，如果用Θ來表示，則必須分成兩條：

1. 最壞的情況下，它的時間複雜度為Θ(n^2)；
2. 最好的情況下，它的時間複雜度為Θ(n)。

這裡的n^{2隻是g(n)這一組函數中最小的上界，當然，g(n)也可以等於n}3。

不過，我們一般說複雜度都是指的最小的上界，比如，這裡插入排序的時間複雜度如果說是O(n^3)，從理論上來說，也沒問題，只是不符合約定罷了。

插入排序最好的情況就是數組本身就是有序的。

o

o定義的也是演算法的上界，不過它不包含等於，是一種不精確的上界，或者稱作松上界（某些書籍翻譯為非緊上界）。

用函數來表示：

對於f(n)，存在正數n0、c，使得當 n>n0 時，始終存在 0 <= f(n) < c*g(n)，則我們可以用 f(n)=o(g(n))表示。

用圖來表示：

o表示僅僅是大O去掉等於的情況，其他行為與大O一模一樣。

Ω

Ω定義了演算法的下界，與O正好相反。

用函數來表示：

對於f(n)，存在正數n0、c，使得當 n>=n0 時，始終存在 0 <= c*g(n) <= f(n)，則我們可以用 f(n)=Ω(g(n))表示。

用圖來表示：

Ω只定義下界，只要f(n)不小於c*g(n)，就可以說 f(n)=Ω(g(n))。

比如，對於插入排序，我們可以說它的時間複雜度為Ω(n)，不過，這通常沒有什麼意義，因為插入排序在最好的情況下很少，基本都是在最壞情況或者平均情況。

ω

ω同樣定義的是下界，只不過不包含等於，是一種不精確的下界，或者稱作松下界（某些書籍翻譯為非緊下界）。

用函數來表示：

對於f(n)，存在正數n0、c，使得當 n>n0 時，始終存在 0 <= c*g(n) < f(n)，則我們可以用 f(n)=ω(g(n))表示。

用圖來表示：

ω表示僅僅是大Ω去掉等於的情況，其他行為與大Ω一模一樣。

通俗理解

小結

為了幫助同學們快速查閱英文資料，彤哥特地把這幾節涉及到的英語單辭彙總了一下：

後記

本節，我們分別從讀音、數學、通俗理解等三個方面闡述了Θ、O、o、Ω、ω的含義，並在最後給出了這幾節涉及到的術語對應的英文，有了這些英文，你也可以快速地查閱這方面的資料。

不過，在我們平時與人交流的過程中，大家還是習慣於使用大O表示法，一來它表示最壞情況，最壞情況通常可以直接代表演算法的複雜度，二來它比較好書寫。

所以，我們只需要記住大O就可以了，只不過在別人提到Θ、Ω、ω我們知道是什麼含義就可以了。

前面幾節講了這麼多，其實，還是只涉及了很簡單的演算法複雜度。

那麼，常見的演算法複雜度有哪些呢？

下一節，我們接著聊。

關注公號主「彤哥讀源碼」，解鎖更多源碼、基礎、架構知識。