復(fù)雜度分析的套路及常見的復(fù)雜度
關(guān)注公眾號“彤哥讀源碼”，解鎖更多源碼、基礎(chǔ)、架構(gòu)知識！
你好，我是彤哥，一個每天爬二十六層樓還不忘讀源碼的硬核男人。
上一節(jié)，我們一起學(xué)習(xí)了表示復(fù)雜度的幾個符號，我們說，通常使用大O來表示算法的復(fù)雜度，不僅合理，而且書寫方便。
那么，使用大O表示法評估算法的復(fù)雜度有沒有什么套路呢？以及常見的復(fù)雜度有哪些呢？
本節(jié)，我們就來解決這兩個問題。
前情回顧在正式講解套路之前，我們先回憶一下前面幾節(jié)講到的內(nèi)容。
在第2節(jié)，我們學(xué)習(xí)了漸近分析法，將算法的復(fù)雜度與輸入規(guī)模掛鉤，隨著輸入規(guī)模的增大，算法執(zhí)行的時間將呈現(xiàn)一種什么樣的趨勢，將這個趨勢用函數(shù)表示，再去除低階項和常數(shù)項，就得到了算法的時間復(fù)雜度。
在第3節(jié)，我們分別從最壞、平均、最好三種情況來分析了算法的復(fù)雜度，得出結(jié)論，一般使用最壞情況來評估算法的復(fù)雜度。
在第4節(jié)，我們通過動態(tài)數(shù)組的插入元素及經(jīng)典快速排序的時間復(fù)雜度，解釋了有的時候不能使用最壞情況來評估算法的復(fù)雜度。
在第5節(jié)，我們從讀音、數(shù)學(xué)、通俗理解三個方面分析了各種表示算法復(fù)雜度的符號，得出結(jié)論還是使用大O比較香，大O代表了算法的上界，它與前面講到的最壞情況往往是對應(yīng)的。
所以，這里所說的套路也是針對大部分情況，也就是最壞情況，對于一些個例，比如經(jīng)典快排，我們雖然也是使用大O表示他們的復(fù)雜度，但是，其實是一種均攤的復(fù)雜度。
好了，讓我們看看計算算法復(fù)雜度的套路到底是什么吧。
套路我將計算算法復(fù)雜度的套路歸納為以下五步：
明確輸入規(guī)模n；
考慮最壞情況或均攤情況，如果最壞情況為個例，那就是均攤；
計算算法執(zhí)行的次數(shù)與n的關(guān)系，并用函數(shù)表示出來；
去除低階項；
去除常數(shù)項；
比如，對于在數(shù)組中查找指定元素的操作：
輸入規(guī)模為數(shù)組的長度n；
考慮最壞情況為目標(biāo)元素不在數(shù)組中；
算法的執(zhí)行次數(shù)為遍歷所有數(shù)組元素，也就是n次，用函數(shù)表示f(n) = n；
去除低階項，沒有低階項，還是n；
去除常數(shù)項，沒有常數(shù)項，還是n；
所以，在數(shù)組中查找指定元素的時間復(fù)雜度為O(n)。
OK，使用這種方式可以很快的計算出算法的復(fù)雜度，也不需要進行額外的計算，非常快捷高效。
常見的復(fù)雜度上面我們說了，復(fù)雜度的計算就是計算與輸入規(guī)模n的關(guān)系，所以，我們想想數(shù)學(xué)中關(guān)于n的函數(shù)就能得出常見的復(fù)雜度了，我繪制了一張表格：
| 與n的關(guān)系 | 英文釋義 | 復(fù)雜度 | 示例 |
|---|---|---|---|
| 常數(shù)（不相關(guān)） | Constant | O(1) | 數(shù)組按索引查找元素 |
| 對數(shù)相關(guān) | Logarithmic | O(logn) | 二分查找 |
| 線性相關(guān) | Linear | O(n) | 遍歷數(shù)組的元素 |
| 超線性相關(guān) | Superlinear | O(nlogn) | 歸并排序、堆排序 |
| 多項式相關(guān) | Polynomial | O(n^c) | 冒泡排序、插入排序、選擇排序 |
| 指數(shù)相關(guān) | Exponential | O(c^n) | 漢諾塔 |
| 階乘相關(guān) | Factorial | O(n!) | 行列式展開 |
| n的n次方 | 無 | O(n^n) | 不知道有沒有這種算法 |
在這張表中，復(fù)雜度是依次增加的，可以看到常數(shù)復(fù)雜度O(1)無疑是最好的，讓我們用一張圖來直觀感受下：
本節(jié)，我們一起學(xué)習(xí)了復(fù)雜度分析的套路以及常見的復(fù)雜度，到目前為止，我們不管是舉例還是講解基本上都在說時間復(fù)雜度。
那么，空間復(fù)雜度又是什么呢？空間與時間之間如何權(quán)衡呢？
下一節(jié)，我們接著聊。