前言

本篇文章收錄于專輯：http://dwz.win/HjK，點(diǎn)擊解鎖更多數(shù)據(jù)結(jié)構(gòu)與算法的知識(shí)。

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

上一節(jié)，我們一起學(xué)習(xí)了表示復(fù)雜度的幾個(gè)符號(hào)，我們說(shuō)，通常使用大O來(lái)表示算法的復(fù)雜度，不僅合理，而且書寫方便。

那么，使用大O表示法評(píng)估算法的復(fù)雜度有沒有什么套路呢？以及常見的復(fù)雜度有哪些呢？

本節(jié)，我們就來(lái)解決這兩個(gè)問(wèn)題。

前情回顧

在正式講解套路之前，我們先回憶一下前面幾節(jié)講到的內(nèi)容。

在第2節(jié)，我們學(xué)習(xí)了漸近分析法，將算法的復(fù)雜度與輸入規(guī)模掛鉤，隨著輸入規(guī)模的增大，算法執(zhí)行的時(shí)間將呈現(xiàn)一種什么樣的趨勢(shì)，將這個(gè)趨勢(shì)用函數(shù)表示，再去除低階項(xiàng)和常數(shù)項(xiàng)，就得到了算法的時(shí)間復(fù)雜度。

在第3節(jié)，我們分別從最壞、平均、最好三種情況來(lái)分析了算法的復(fù)雜度，得出結(jié)論，一般使用最壞情況來(lái)評(píng)估算法的復(fù)雜度。

在第4節(jié)，我們通過(guò)動(dòng)態(tài)數(shù)組的插入元素及經(jīng)典快速排序的時(shí)間復(fù)雜度，解釋了有的時(shí)候不能使用最壞情況來(lái)評(píng)估算法的復(fù)雜度。

在第5節(jié)，我們從讀音、數(shù)學(xué)、通俗理解三個(gè)方面分析了各種表示算法復(fù)雜度的符號(hào)，得出結(jié)論還是使用大O比較香，大O代表了算法的上界，它與前面講到的最壞情況往往是對(duì)應(yīng)的。

所以，這里所說(shuō)的套路也是針對(duì)大部分情況，也就是最壞情況，對(duì)于一些個(gè)例，比如經(jīng)典快排，我們雖然也是使用大O表示他們的復(fù)雜度，但是，其實(shí)是一種均攤的復(fù)雜度。

好了，讓我們看看計(jì)算算法復(fù)雜度的套路到底是什么吧。

套路

我將計(jì)算算法復(fù)雜度的套路歸納為以下五步：

1. 明確輸入規(guī)模n；
2. 考慮最壞情況或均攤情況，如果最壞情況為個(gè)例，那就是均攤；
3. 計(jì)算算法執(zhí)行的次數(shù)與n的關(guān)系，并用函數(shù)表示出來(lái)；
4. 去除低階項(xiàng)；
5. 去除常數(shù)項(xiàng)；

比如，對(duì)于在數(shù)組中查找指定元素的操作：

1. 輸入規(guī)模為數(shù)組的長(zhǎng)度n；
2. 考慮最壞情況為目標(biāo)元素不在數(shù)組中；
3. 算法的執(zhí)行次數(shù)為遍歷所有數(shù)組元素，也就是n次，用函數(shù)表示f(n) = n；
4. 去除低階項(xiàng)，沒有低階項(xiàng)，還是n；
5. 去除常數(shù)項(xiàng)，沒有常數(shù)項(xiàng)，還是n；

所以，在數(shù)組中查找指定元素的時(shí)間復(fù)雜度為O(n)。

OK，使用這種方式可以很快的計(jì)算出算法的復(fù)雜度，也不需要進(jìn)行額外的計(jì)算，非?？旖莞咝А?/p>

常見的復(fù)雜度

上面我們說(shuō)了，復(fù)雜度的計(jì)算就是計(jì)算與輸入規(guī)模n的關(guān)系，所以，我們想想數(shù)學(xué)中關(guān)于n的函數(shù)就能得出常見的復(fù)雜度了，我繪制了一張表格：

在這張表中，復(fù)雜度是依次增加的，可以看到常數(shù)復(fù)雜度O(1)無(wú)疑是最好的，讓我們用一張圖來(lái)直觀感受下：

后記

本節(jié)，我們一起學(xué)習(xí)了復(fù)雜度分析的套路以及常見的復(fù)雜度，到目前為止，我們不管是舉例還是講解基本上都在說(shuō)時(shí)間復(fù)雜度。

那么，空間復(fù)雜度又是什么呢？空間與時(shí)間之間如何權(quán)衡呢？

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

關(guān)注公號(hào)主“彤哥讀源碼”，解鎖更多源碼、基礎(chǔ)、架構(gòu)知識(shí)。