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