關(guān)注公眾號“彤哥讀源碼”，解鎖更多源碼、基礎(chǔ)、架構(gòu)知識！

前言

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

前面幾節(jié)，我們一起學(xué)習(xí)了算法的復(fù)雜度如何分析，并從最壞、平均、最好以及不能使用最壞情況全方位無死角的剖析了算法的復(fù)雜度，在我們表示復(fù)雜度的時候，通常使用大O來表示。

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

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

本節(jié)，我們就來解決這個問題。

讀音

我們先來糾正一波讀音：

• O，/??/，大Oh

• o，/??/，小oh

• Θ，/?θi?t?/，theta

• Ω，/o??meɡ?/，大Omega

• ω，/o??meɡ?/，小omega

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

數(shù)學(xué)解釋

Θ

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

用函數(shù)來表示：

對于f(n)，存在正數(shù)n0、c1、c2，使得當(dāng) 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)去掉低階項和常數(shù)項得來的，因為肯定存在某個正數(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ù)。

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

O

O定義了算法的上界。

用函數(shù)來表示：

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

用圖來表示：

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

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

1. 最壞的情況下，它的時間復(fù)雜度為Θ(n^2)；

2. 最好的情況下，它的時間復(fù)雜度為Θ(n)。

這里的n^2只是g(n)這一組函數(shù)中最小的上界，當(dāng)然，g(n)也可以等于n^3。

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

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

o

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

用函數(shù)來表示：

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

用圖來表示：

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

Ω

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

用函數(shù)來表示：

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

用圖來表示：

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

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

ω

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

用函數(shù)來表示：

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

用圖來表示：

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

通俗理解

符號	含義	通俗理解
Θ	精確的漸近行為	相當(dāng)于“=”
O	上界	相當(dāng)于“<=”
o	松上界	相當(dāng)于“<”
Ω	下界	相當(dāng)于“>=”
ω	松下界	相當(dāng)于“>”

小結(jié)

為了幫助同學(xué)們快速查閱英文資料，彤哥特地把這幾節(jié)涉及到的英語單詞匯總了一下：

漢語	英文
復(fù)雜度	complexity
時間復(fù)雜度	time complexity
空間復(fù)雜度	space complexity
漸近分析	asymptotic analysis
最壞情況	the worst case
最好情況	the best case
平均情況	the average case
精確的漸近行為	exact asymptotic behavior
低階項	low order terms
常數(shù)項（前置常數(shù)）	leading constants
松上界	loose upper-bound

后記

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

不過，在我們平時與人交流的過程中，大家還是習(xí)慣于使用大O表示法，一來它表示最壞情況，最壞情況通?？梢灾苯哟硭惴ǖ膹?fù)雜度，二來它比較好書寫。

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

前面幾節(jié)講了這么多，其實，還是只涉及了很簡單的算法復(fù)雜度。

那么，常見的算法復(fù)雜度有哪些呢？

下一節(jié)，我們接著聊。