算法（Algorithm）是指用來操作數據、解決程序問題的一組方法。對于同一個問題，使用不同的算法，也許最終得到的結果是一樣的，比如排序就有前面的十大經典排序和幾種奇葩排序，雖然結果相同，但在過程中消耗的資源和時間卻會有很大的區別，比如快速排序與猴子排序：）。

那么我們應該如何去衡量不同算法之間的優劣呢？

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

時間維度：是指執行當前算法所消耗的時間，我們通常用「時間復雜度」來描述。

空間維度：是指執行當前算法需要占用多少內存空間，我們通常用「空間復雜度」來描述。

本小節將從「時間」的維度進行分析。

什么是大O

當看「時間」二字，我們肯定可以想到將該算法程序運行一篇，通過運行的時間很容易就知道復雜度了。

這種方式可以嗎？當然可以，不過它也有很多弊端。

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

那有什么方法可以嚴謹的進行算法的時間復雜度分析呢？

有的!

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

其中 n 表示數據規模 ，O(f(n))表示運行算法所需要執行的指令數，和f(n)成正比。

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

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

常見的時間復雜度量級

我們先從常見的時間復雜度量級進行大O的理解：

常數階O(1)

線性階O(n)

平方階O(n2)

對數階O(logn)

線性對數階O(nlogn)

O(1)

無論代碼執行了多少行，其他區域不會影響到操作，這個代碼的時間復雜度都是O(1)

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

O(n)

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

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)

當存在雙重循環的時候，即把 O(n) 的代碼再嵌套循環一遍，它的時間復雜度就是 O(n2) 了。

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

這里簡單的推導一下

當 i = 0 時，第二重循環需要運行 (n - 1) 次

當 i = 1 時，第二重循環需要運行 (n - 2) 次

。。。。。。

不難得到公式：

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

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

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}

在二分查找法的代碼中，通過while循環，成 2 倍數的縮減搜索范圍，也就是說需要經過 log2^n 次即可跳出循環。

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

1//整形轉成字符串 2stringintToString(intnum){ 3strings=""; 4//n經過幾次“除以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)

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

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

上面講述了與復雜度有關的大 O 表示法和常見的時間復雜度量級，這篇文章來講講另外幾種復雜度： 遞歸算法的時間復雜度（recursive algorithm time complexity），最好情況時間復雜度（best case time complexity）、最壞情況時間復雜度（worst case time complexity）、平均時間復雜度（average case time complexity）和均攤時間復雜度（amortized time complexity）。

遞歸算法的時間復雜度

如果遞歸函數中，只進行一次遞歸調用，遞歸深度為depth；

在每個遞歸的函數中，時間復雜度為T；

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

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

① 遞歸中進行一次遞歸調用的復雜度分析

二分查找法

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 ] 范圍中去查找目標的位置，如果中間的元素arr[mid]不是target，那么判斷arr[mid]是比target大 還是 小 ，進而再次調用binarySearch這個函數。

在這個遞歸函數中，每一次沒有找到target時，要么調用 左邊 的binarySearch函數，要么調用 右邊 的binarySearch函數。也就是說在此次遞歸中，最多調用了一次遞歸調用而已。根據數學知識，需要log2n次才能遞歸到底。因此，二分查找法的時間復雜度為 O(logn)。

求和

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

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

求冪

1//遞歸深度：logn2//時間復雜度：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，因為是求需要除以 2 多少次才能到底。

② 遞歸中進行多次遞歸調用的復雜度分析

遞歸算法中比較難計算的是多次遞歸調用。

先看下面這段代碼，有兩次遞歸調用。

1//O(2^n)指數級別的數量級，后續動態規劃的優化點2intf(intn){3if(n==0)return1;4returnf(n-1)+f(n-1);5}

遞歸樹中節點數就是代碼計算的調用次數。

比如 當n = 3時，調用次數計算公式為

1 + 2 + 4 + 8 = 15

一般的，調用次數計算公式為

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

與之有所類似的是 歸并排序 的遞歸樹，區別點在于

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

2. 上述例子中每次處理的數據規模是一樣的，而在 歸并排序 中每個節點處理的數據規模是逐漸縮小的

因此，在如 歸并排序 等排序算法中，每一層處理的數據量為 O(n) 級別，同時有logn層，時間復雜度便是 O(nlogn)。

最好、最壞情況時間復雜度

最好、最壞情況時間復雜度指的是特殊情況下的時間復雜度。

動圖表明的是在數組 array 中尋找變量 x 第一次出現的位置，若沒有找到，則返回 -1；否則返回位置下標。

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

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

最好情況時間復雜度就是在最理想情況下執行代碼的時間復雜度，它的時間是最短的；最壞情況時間復雜度就是在最糟糕情況下執行代碼的時間復雜度，它的時間是最長的。

平均情況時間復雜度

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

平均情況時間復雜度可用代碼在所有可能情況下執行次數的加權平均值表示。

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

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

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

均攤復雜度分析

我們通過一個動態數組的push_back操作來理解均攤復雜度。

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

push_back實現的功能是往數組的末尾增加一個元素，如果數組沒有滿，直接往后面插入元素；如果數組滿了，即size == capacity，則將數組擴容一倍，然后再插入元素。

例如，數組長度為 n，則前 n 次調用push_back復雜度都為 O(1) 級別；在第 n + 1 次則需要先進行 n 次元素轉移操作，然后再進行 1 次插入操作，復雜度為 O(n)。

因此，平均來看：對于容量為 n 的動態數組，前面添加元素需要消耗了 1 * n 的時間，擴容操作消耗 n 時間 ，總共就是 2 * n 的時間，因此均攤時間復雜度為 O(2n / n) = O(2)，也就是 O(1) 級別了。

可以得出一個比較有意思的結論：一個相對比較耗時的操作，如果能保證它不會每次都被觸發，那么這個相對比較耗時的操作，它所相應的時間是可以分攤到其它的操作中來的。