算法（Algorithm）是指用來(lái)操作數(shù)據(jù)、解決程序問(wèn)題的一組方法。對(duì)于同一個(gè)問(wèn)題，使用不同的算法，也許最終得到的結(jié)果是一樣的，比如排序就有前面的十大經(jīng)典排序和幾種奇葩排序，雖然結(jié)果相同，但在過(guò)程中消耗的資源和時(shí)間卻會(huì)有很大的區(qū)別，比如快速排序與猴子排序：）。

那么我們應(yīng)該如何去衡量不同算法之間的優(yōu)劣呢？

主要還是從算法所占用的「時(shí)間」和「空間」兩個(gè)維度去考量。

時(shí)間維度：是指執(zhí)行當(dāng)前算法所消耗的時(shí)間，我們通常用「時(shí)間復(fù)雜度」來(lái)描述。

空間維度：是指執(zhí)行當(dāng)前算法需要占用多少內(nèi)存空間，我們通常用「空間復(fù)雜度」來(lái)描述。

本小節(jié)將從「時(shí)間」的維度進(jìn)行分析。

什么是大O

當(dāng)看「時(shí)間」二字，我們肯定可以想到將該算法程序運(yùn)行一篇，通過(guò)運(yùn)行的時(shí)間很容易就知道復(fù)雜度了。

這種方式可以嗎？當(dāng)然可以，不過(guò)它也有很多弊端。

比如程序員小吳的老式電腦處理10w數(shù)據(jù)使用冒泡排序要幾秒，但讀者的iMac Pro 可能只需要0.1s，這樣的結(jié)果誤差就很大了。更何況，有的算法運(yùn)行時(shí)間要很久，根本沒(méi)辦法沒(méi)時(shí)間去完整的運(yùn)行，還是比如猴子排序：）。

那有什么方法可以嚴(yán)謹(jǐn)?shù)倪M(jìn)行算法的時(shí)間復(fù)雜度分析呢？

有的!

「 遠(yuǎn)古 」的程序員大佬們提出了通用的方法：「 大O符號(hào)表示法 」，即T(n) = O(f(n))。

其中 n 表示數(shù)據(jù)規(guī)模 ，O(f(n))表示運(yùn)行算法所需要執(zhí)行的指令數(shù)，和f(n)成正比。

上面公式中用到的 Landau符號(hào)是由德國(guó)數(shù)論學(xué)家保羅·巴赫曼（Paul Bachmann）在其1892年的著作《解析數(shù)論》首先引入，由另一位德國(guó)數(shù)論學(xué)家艾德蒙·朗道（Edmund Landau）推廣。Landau符號(hào)的作用在于用簡(jiǎn)單的函數(shù)來(lái)描述復(fù)雜函數(shù)行為，給出一個(gè)上或下（確）界。在計(jì)算算法復(fù)雜度時(shí)一般只用到大O符號(hào)，Landau符號(hào)體系中的小o符號(hào)、Θ符號(hào)等等比較不常用。這里的O，最初是用大寫希臘字母，但現(xiàn)在都用大寫英語(yǔ)字母O；小o符號(hào)也是用小寫英語(yǔ)字母o，Θ符號(hào)則維持大寫希臘字母Θ。

注：本文用到的算法中的界限指的是最低的上界。

常見(jiàn)的時(shí)間復(fù)雜度量級(jí)

我們先從常見(jiàn)的時(shí)間復(fù)雜度量級(jí)進(jìn)行大O的理解：

常數(shù)階O(1)

線性階O(n)

平方階O(n2)

對(duì)數(shù)階O(logn)

線性對(duì)數(shù)階O(nlogn)

O(1)

無(wú)論代碼執(zhí)行了多少行，其他區(qū)域不會(huì)影響到操作，這個(gè)代碼的時(shí)間復(fù)雜度都是O(1)

1voidswapTwoInts(int&a,int&b){2inttemp=a;3a=b;4b=temp;5}

O(n)

在下面這段代碼，for循環(huán)里面的代碼會(huì)執(zhí)行 n 遍，因此它消耗的時(shí)間是隨著 n 的變化而變化的，因此可以用O(n)來(lái)表示它的時(shí)間復(fù)雜度。

1intsum(intn){2intret=0;3for(inti=0;i<=?n?;?i?++){4??????ret?+=?i;5???}6???return?ret;7}

特別一提的是 c * O(n) 中的 c 可能小于 1 ，比如下面這段代碼：

1voidreverse(string&s){2intn=s.size();3for(inti=0;i

O(n2)

當(dāng)存在雙重循環(huán)的時(shí)候，即把 O(n) 的代碼再嵌套循環(huán)一遍，它的時(shí)間復(fù)雜度就是 O(n2) 了。

1voidselectionSort(intarr[],intn){ 2for(inti=0;i

這里簡(jiǎn)單的推導(dǎo)一下

當(dāng) i = 0 時(shí)，第二重循環(huán)需要運(yùn)行 (n - 1) 次

當(dāng) i = 1 時(shí)，第二重循環(huán)需要運(yùn)行 (n - 2) 次

。。。。。。

不難得到公式：

1(n-1)+(n-2)+(n-3)+...+02=(0+n-1)*n/23=O(n^2)

當(dāng)然并不是所有的雙重循環(huán)都是 O(n2)，比如下面這段輸出 30n 次 Hello,五分鐘學(xué)算法：）的代碼。

1voidprintInformation(intn){2for(inti=1;i<=?n?;?i++)3????????for?(int?j?=?1?;?j?<=?30?;?j?++)4???????????cout<

O(logn)

1intbinarySearch(intarr[],intn,inttarget){ 2intl=0,r=n-1; 3while(l<=?r)?{ 4????int?mid?=?l?+?(r?-?l)?/?2; 5????if?(arr[mid]?==?target)?return?mid; 6????if?(arr[mid]?>target)r=mid-1; 7elsel=mid+1; 8} 9return-1;10}

在二分查找法的代碼中，通過(guò)while循環(huán)，成 2 倍數(shù)的縮減搜索范圍，也就是說(shuō)需要經(jīng)過(guò) log2^n 次即可跳出循環(huán)。

同樣的還有下面兩段代碼也是 O(logn) 級(jí)別的時(shí)間復(fù)雜度。

1//整形轉(zhuǎn)成字符串 2stringintToString(intnum){ 3strings=""; 4//n經(jīng)過(guò)幾次“除以10”的操作后，等于0 5while(num){ 6s+='0'+num%10; 7num/=10; 8} 9reverse(s)10returns;11}1voidhello(intn){2//n除以幾次2到13for(intsz=1;sz

O(nlogn)

將時(shí)間復(fù)雜度為O(logn)的代碼循環(huán)N遍的話，那么它的時(shí)間復(fù)雜度就是 n * O(logn)，也就是了O(nlogn)。

1voidhello(){2for(m=1;m

上面講述了與復(fù)雜度有關(guān)的大 O 表示法和常見(jiàn)的時(shí)間復(fù)雜度量級(jí)，這篇文章來(lái)講講另外幾種復(fù)雜度： 遞歸算法的時(shí)間復(fù)雜度（recursive algorithm time complexity），最好情況時(shí)間復(fù)雜度（best case time complexity）、最壞情況時(shí)間復(fù)雜度（worst case time complexity）、平均時(shí)間復(fù)雜度（average case time complexity）和均攤時(shí)間復(fù)雜度（amortized time complexity）。

遞歸算法的時(shí)間復(fù)雜度

如果遞歸函數(shù)中，只進(jìn)行一次遞歸調(diào)用，遞歸深度為depth；

在每個(gè)遞歸的函數(shù)中，時(shí)間復(fù)雜度為T；

則總體的時(shí)間復(fù)雜度為O(T * depth)。

在前面的學(xué)習(xí)中，歸并排序 與 快速排序 都帶有遞歸的思想，并且時(shí)間復(fù)雜度都是O(nlogn) ，但并不是有遞歸的函數(shù)就一定是 O(nlogn) 級(jí)別的。從以下兩種情況進(jìn)行分析。

① 遞歸中進(jìn)行一次遞歸調(diào)用的復(fù)雜度分析

二分查找法

1intbinarySearch(intarr[],intl,intr,inttarget){ 2if(l>r)return-1; 3 4intmid=l+(r-l)/2; 5if(arr[mid]==target)returnmid; 6elseif(arr[mid]>target) 7returnbinarySearch(arr,l,mid-1,target);//左邊 8else 9returnbinarySearch(arr,mid+1,r,target);//右邊10}

比如在這段二分查找法的代碼中，每次在 [ l , r ] 范圍中去查找目標(biāo)的位置，如果中間的元素arr[mid]不是target，那么判斷arr[mid]是比target大 還是 小 ，進(jìn)而再次調(diào)用binarySearch這個(gè)函數(shù)。

在這個(gè)遞歸函數(shù)中，每一次沒(méi)有找到target時(shí)，要么調(diào)用 左邊 的binarySearch函數(shù)，要么調(diào)用 右邊 的binarySearch函數(shù)。也就是說(shuō)在此次遞歸中，最多調(diào)用了一次遞歸調(diào)用而已。根據(jù)數(shù)學(xué)知識(shí)，需要log2n次才能遞歸到底。因此，二分查找法的時(shí)間復(fù)雜度為 O(logn)。

求和

1intsum(intn){2if(n==0)return0;3returnn+sum(n-1)4}

在這段代碼中比較容易理解遞歸深度隨輸入 n 的增加而線性遞增，因此時(shí)間復(fù)雜度為 O (n)。

求冪

1//遞歸深度：logn2//時(shí)間復(fù)雜度：O(logn)3doublepow(doublex,intn){4if(n==0)return1.0;56doublet=pow(x,n/2);7if(n%2)returnx*t*t;8returnt*t;9}

遞歸深度為logn，因?yàn)槭乔笮枰?2 多少次才能到底。

② 遞歸中進(jìn)行多次遞歸調(diào)用的復(fù)雜度分析

遞歸算法中比較難計(jì)算的是多次遞歸調(diào)用。

先看下面這段代碼，有兩次遞歸調(diào)用。

1//O(2^n)指數(shù)級(jí)別的數(shù)量級(jí)，后續(xù)動(dòng)態(tài)規(guī)劃的優(yōu)化點(diǎn)2intf(intn){3if(n==0)return1;4returnf(n-1)+f(n-1);5}

遞歸樹(shù)中節(jié)點(diǎn)數(shù)就是代碼計(jì)算的調(diào)用次數(shù)。

比如 當(dāng)n = 3時(shí)，調(diào)用次數(shù)計(jì)算公式為

1 + 2 + 4 + 8 = 15

一般的，調(diào)用次數(shù)計(jì)算公式為

2^0 + 2^1 + 2^2 + …… + 2^n= 2^(n+1) - 1= O(2^n)

與之有所類似的是 歸并排序 的遞歸樹(shù)，區(qū)別點(diǎn)在于

1. 上述例子中樹(shù)的深度為n，而 歸并排序 的遞歸樹(shù)深度為logn。

2. 上述例子中每次處理的數(shù)據(jù)規(guī)模是一樣的，而在 歸并排序 中每個(gè)節(jié)點(diǎn)處理的數(shù)據(jù)規(guī)模是逐漸縮小的

因此，在如 歸并排序 等排序算法中，每一層處理的數(shù)據(jù)量為 O(n) 級(jí)別，同時(shí)有l(wèi)ogn層，時(shí)間復(fù)雜度便是 O(nlogn)。

最好、最壞情況時(shí)間復(fù)雜度

最好、最壞情況時(shí)間復(fù)雜度指的是特殊情況下的時(shí)間復(fù)雜度。

動(dòng)圖表明的是在數(shù)組 array 中尋找變量 x 第一次出現(xiàn)的位置，若沒(méi)有找到，則返回 -1；否則返回位置下標(biāo)。

1intfind(int[]array,intn,intx){2for(inti=0;i

在這里當(dāng)數(shù)組中第一個(gè)元素就是要找的 x 時(shí)，時(shí)間復(fù)雜度是 O(1)；而當(dāng)最后一個(gè)元素才是 x 時(shí)，時(shí)間復(fù)雜度則是 O(n)。

最好情況時(shí)間復(fù)雜度就是在最理想情況下執(zhí)行代碼的時(shí)間復(fù)雜度，它的時(shí)間是最短的；最壞情況時(shí)間復(fù)雜度就是在最糟糕情況下執(zhí)行代碼的時(shí)間復(fù)雜度，它的時(shí)間是最長(zhǎng)的。

平均情況時(shí)間復(fù)雜度

最好、最壞時(shí)間復(fù)雜度反應(yīng)的是極端條件下的復(fù)雜度，發(fā)生的概率不大，不能代表平均水平。那么為了更好的表示平均情況下的算法復(fù)雜度，就需要引入平均時(shí)間復(fù)雜度。

平均情況時(shí)間復(fù)雜度可用代碼在所有可能情況下執(zhí)行次數(shù)的加權(quán)平均值表示。

還是以find函數(shù)為例，從概率的角度看， x 在數(shù)組中每一個(gè)位置的可能性是相同的，為 1 / n。那么，那么平均情況時(shí)間復(fù)雜度就可以用下面的方式計(jì)算：

((1 + 2 + … + n) / n + n) / 2 = (3n + 1) / 4

find函數(shù)的平均時(shí)間復(fù)雜度為 O(n)。

均攤復(fù)雜度分析

我們通過(guò)一個(gè)動(dòng)態(tài)數(shù)組的push_back操作來(lái)理解均攤復(fù)雜度。

1template 2classMyVector{ 3private: 4T*data; 5intsize;//存儲(chǔ)數(shù)組中的元素個(gè)數(shù) 6intcapacity;//存儲(chǔ)數(shù)組中可以容納的最大的元素個(gè)數(shù) 7//復(fù)雜度為O(n) 8voidresize(intnewCapacity){ 9T*newData=newT[newCapacity];10for(inti=0;i

push_back實(shí)現(xiàn)的功能是往數(shù)組的末尾增加一個(gè)元素，如果數(shù)組沒(méi)有滿，直接往后面插入元素；如果數(shù)組滿了，即size == capacity，則將數(shù)組擴(kuò)容一倍，然后再插入元素。

例如，數(shù)組長(zhǎng)度為 n，則前 n 次調(diào)用push_back復(fù)雜度都為 O(1) 級(jí)別；在第 n + 1 次則需要先進(jìn)行 n 次元素轉(zhuǎn)移操作，然后再進(jìn)行 1 次插入操作，復(fù)雜度為 O(n)。

因此，平均來(lái)看：對(duì)于容量為 n 的動(dòng)態(tài)數(shù)組，前面添加元素需要消耗了 1 * n 的時(shí)間，擴(kuò)容操作消耗 n 時(shí)間 ，總共就是 2 * n 的時(shí)間，因此均攤時(shí)間復(fù)雜度為 O(2n / n) = O(2)，也就是 O(1) 級(jí)別了。

可以得出一個(gè)比較有意思的結(jié)論：一個(gè)相對(duì)比較耗時(shí)的操作，如果能保證它不會(huì)每次都被觸發(fā)，那么這個(gè)相對(duì)比較耗時(shí)的操作，它所相應(yīng)的時(shí)間是可以分?jǐn)偟狡渌牟僮髦衼?lái)的。