算法（Algorithm）是指用來操作資料、解決程式問題的一組方法。對于同一個問題，使用不同的算法，也許最終得到的結果是一樣的，比如排序就有前面的十大經典排序和幾種奇葩排序，雖然結果相同，但在過程中消耗的資源和時間卻會有很大的差別，比如快速排序與猴子排序：）。
那麼我們應該如何去衡量不同算法之間的優劣呢？
主要還是從算法所占用的「時間」和「空間」兩個次元去考量。
- 時間次元：是指執行目前算法所消耗的時間，我們通常用「時間複雜度」來描述。
- 空間次元：是指執行目前算法需要占用多少記憶體空間，我們通常用「空間複雜度」來描述。
冰之哀傷：時間複雜度
大O符号表示法
大O表示法：算法的時間複雜度通常用大O符号表述，定義為
**T[n] = O(f(n)) **
。稱函數T(n)以f(n)為界或者稱T(n)受限于f(n)。
如果一個問題的規模是n，解這一問題的某一算法所需要的時間為T(n)。T(n)稱為這一算法的“時間複雜度”。
上面公式中用到的 Landau符号是由德國數論學家保羅·巴赫曼（Paul Bachmann）在其1892年的著作《解析數論》首先引入，由另一位德國數論學家艾德蒙·朗道（Edmund Landau）推廣。Landau符号的作用在于用簡單的函數來描述複雜函數行為，給出一個上或下（确）界。在計算算法複雜度時一般隻用到大O符号，Landau符号體系中的小o符号、Θ符号等等比較不常用。這裡的O，最初是用大寫希臘字母，但現在都用大寫英語字母O；小o符号也是用小寫英語字母o，Θ符号則維持大寫希臘字母Θ。
大O符号是一種算法「複雜度」的「相對」「表示」方式。
這個句子裡有一些重要而嚴謹的用詞：
- 相對(relative)：你隻能比較相同的事物。你不能把一個做算數乘法的算法和排序整數清單的算法進行比較。但是，比較2個算法所做的算術操作（一個做乘法，一個做加法）将會告訴你一些有意義的東西；
- 表示(representation)：大O(用它最簡單的形式)把算法間的比較簡化為了一個單一變量。這個變量的選擇基于觀察或假設。例如，排序算法之間的對比通常是基于比較操作(比較2個結點來決定這2個結點的相對順序)。這裡面就假設了比較操作的計算開銷很大。但是，如果比較操作的計算開銷不大，而交換操作的計算開銷很大，又會怎麼樣呢？這就改變了先前的比較方式；
- 複雜度(complexity)：如果排序10,000個元素花費了我1秒，那麼排序1百萬個元素會花多少時間？在這個例子裡，複雜度就是相對其他東西的度量結果。
常見的時間複雜度量級
我們先從常見的時間複雜度量級進行大O的了解：
- 常數階O(1)
- 線性階O(n)
- 平方階O(n²)
- 對數階O(logn)
- 線性對數階O(nlogn)
無論代碼執行了多少行，其他區域不會影響到操作，這個代碼的時間複雜度都是O(1)
1 void swapTwoInts(int &a, int &b){
2 int temp = a;
3 a = b;
4 b = temp;
5 } O (n)
在下面這段代碼，for循環裡面的代碼會執行 n 遍，是以它消耗的時間是随着 n 的變化而變化的，是以可以用O(n)來表示它的時間複雜度。
1 int sum ( int n ){
2 int ret = 0;
3 for ( int i = 0 ; i <= n ; i ++){
4 ret += i;
5 }
6 return ret;
7 } 特别一提的是 c * O(n) 中的 c 可能小于 1 ，比如下面這段代碼：
1 void reverse ( string &s ) {
2 int n = s.size();
3 for (int i = 0 ; i < n/2 ; i++){
4 swap ( s[i] , s[n-1-i]);
5 }
6 } O(n²)
當存在雙重循環的時候，即把 O(n) 的代碼再嵌套循環一遍，它的時間複雜度就是 O(n²) 了。
1 void selectionSort(int arr[],int n){
2 for(int i = 0; i < n ; i++){
3 int minIndex = i;
4 for (int j = i + 1; j < n ; j++ )
5 if (arr[j] < arr[minIndex])
6 minIndex = j;
7
8 swap ( arr[i], arr[minIndex]);
9 }
10 } 這裡簡單的推導一下
- 當 i = 0 時，第二重循環需要運作 (n – 1) 次
- 當 i = 1 時，第二重循環需要運作 (n – 2) 次
- 。。。。。。
不難得到公式：
1 (n - 1) + (n - 2) + (n - 3) + ... + 0
2 = (0 + n - 1) * n / 2
3 = O (n ^2) 當然并不是所有的雙重循環都是 O(n²)，比如下面這段輸出 30n 次 Hello,五分鐘學算法：）的代碼。
1 void printInformation (int n ){
2 for (int i = 1 ; i <= n ; i++)
3 for (int j = 1 ; j <= 30 ; j ++)
4 cout<< "Hello,五分鐘學算法：）"<< endl;
5 }
O(logn)
1 int binarySearch( int arr[], int n , int target){
2 int l = 0, r = n - 1;
3 while ( l <= r) {
4 int mid = l + (r - l) / 2;
5 if (arr[mid] == target) return mid;
6 if (arr[mid] > target ) r = mid - 1;
7 else l = mid + 1;
8 }
9 return -1;
10 } 在二分查找法的代碼中，通過while循環，成 2 倍數的縮減搜尋範圍，也就是說需要經過 log2^n 次即可跳出循環。
同樣的還有下面兩段代碼也是 O(logn) 級别的時間複雜度。
1 // 整形轉成字元串
2 string intToString ( int num ){
3 string s = "";
4 // n 經過幾次“除以10”的操作後，等于0
5 while (num ){
6 s += '0' + num%10;
7 num /= 10;
8 }
9 reverse(s)
10 return s;
11 }
1void hello (int n ) {
2 // n 除以幾次 2 到 1
3 for ( int sz = 1; sz < n ; sz += sz)
4 for (int i = 1; i < n; i++)
5 cout<< "Hello,五分鐘學算法：）"<< endl;
6 } O(nlogn)
将時間複雜度為O(logn)的代碼循環N遍的話，那麼它的時間複雜度就是 n * O(logn)，也就是了O(nlogn)。
1void hello (){
2 for( m = 1 ; m < n ; m++){
3 i = 1;
4 while( i < n ){
5 i = i * 2;
6 }
7 }
8} 不常見的時間複雜度
下面來分析一波另外幾種複雜度： 遞歸算法的時間複雜度（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) 級别的。從以下兩種情況進行分析。
① 遞歸中進行一次遞歸調用的複雜度分析
二分查找法
1int binarySearch(int arr[], int l, int r, int target){
2 if( l > r ) return -1;
3
4 int mid = l + (r-l)/2;
5 if( arr[mid] == target ) return mid;
6 else if( arr[mid] > target )
7 return binarySearch(arr, l, mid-1, target); // 左邊
8 else
9 return binarySearch(arr, mid+1, r, target); // 右邊
10} 比如在這段二分查找法的代碼中，每次在 [ l , r ] 範圍中去查找目标的位置，如果中間的元素 arr[mid] 不是 target，那麼判斷 arr[mid]是比 target 大 還是 小 ，進而再次調用 binarySearch這個函數。
在這個遞歸函數中，每一次沒有找到target時，要麼調用 左邊 的 binarySearch函數，要麼調用 右邊 的 binarySearch函數。也就是說在此次遞歸中，最多調用了一次遞歸調用而已。根據數學知識，需要log2n次才能遞歸到底。是以，二分查找法的時間複雜度為 O(logn)。
求和
1int sum (int n) {
2 if (n == 0) return 0;
3 return n + sum( n - 1 )
4} 在這段代碼中比較容易了解遞歸深度随輸入 n 的增加而線性遞增，是以時間複雜度為 O (n)。
求幂
1//遞歸深度：logn
2//時間複雜度：O(logn)
3double pow( double x, int n){
4 if (n == 0) return 1.0;
5
6 double t = pow(x,n/2);
7 if (n %2) return x*t*t;
8 return t * t;
9}
遞歸深度為 logn，因為是求需要除以 2 多少次才能到底。
② 遞歸中進行多次遞歸調用的複雜度分析
遞歸算法中比較難計算的是多次遞歸調用。
先看下面這段代碼，有兩次遞歸調用。
1// O(2^n) 指數級别的數量級，後續動态規劃的優化點
2int f(int n){
3 if (n == 0) return 1;
4 return f(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)
與之有所類似的是 歸并排序 的遞歸樹，差別點在于
-
- 上述例子中樹的深度為 n，而 歸并排序 的遞歸樹深度為logn。
-
- 上述例子中每次處理的資料規模是一樣的，而在 歸并排序 中每個節點處理的資料規模是逐漸縮小的
是以，在如 歸并排序 等排序算法中，每一層處理的資料量為 O(n) 級别，同時有 logn 層，時間複雜度便是 O(nlogn)。
最好、最壞情況時間複雜度
最好、最壞情況時間複雜度指的是特殊情況下的時間複雜度。
動圖表明的是在數組 array 中尋找變量 x 第一次出現的位置，若沒有找到，則傳回 -1；否則傳回位置下标。
1int find(int[] array, int n, int x) {
2 for ( int i = 0 ; i < n; i++) {
3 if (array[i] == x) {
4 return i;
5 break;
6 }
7 }
8 return -1;
9}
在這裡當數組中第一個元素就是要找的 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 <typename T>
2class MyVector{
3private:
4 T* data;
5 int size; // 存儲數組中的元素個數
6 int capacity; // 存儲數組中可以容納的最大的元素個數
7 // 複雜度為 O(n)
8 void resize(int newCapacity){
9 T *newData = new T[newCapacity];
10 for( int i = 0 ; i < size ; i ++ ){
11 newData[i] = data[i];
12 }
13 data = newData;
14 capacity = newCapacity;
15 }
16public:
17 MyVector(){
18 data = new T[100];
19 size = 0;
20 capacity = 100;
21 }
22 // 平均複雜度為 O(1)
23 void push_back(T e){
24 if(size == capacity)
25 resize(2 * capacity);
26 data[size++] = e;
27 }
28 // 平均複雜度為 O(1)
29 T pop_back(){
30 size --;
31 return data[size];
32 }
33
34}; 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) 級别了。
可以得出一個比較有意思的結論：一個相對比較耗時的操作，如果能保證它不會每次都被觸發，那麼這個相對比較耗時的操作，它所相應的時間是可以分攤到其它的操作中來的。
火之晨曦：空間複雜度
🔥🔥🔥🔥，到處都是🔥
一個程式的空間複雜度是指運作完一個程式所需記憶體的大小。利用程式的空間複雜度，可以對程式的運作所需要的記憶體多少有個預先估計。一個程式執行時除了需要存儲空間和存儲本身所使用的指令、常數、變量和輸入資料外，還需要一些對資料進行操作的工作單元和存儲一些為現實計算所需資訊的輔助空間。程式執行時所需存儲空間包括以下兩部分：
(1) 固定部分，這部分空間的大小與輸入/輸出的資料的個數多少、數值無關。主要包括指令空間（即代碼空間）、資料空間（常量、簡單變量）等所占的空間。這部分屬于靜态空間。
(2) 可變空間，這部分空間的主要包括動态配置設定的空間，以及遞歸棧所需的空間等。這部分的空間大小與算法有關。
一個算法所需的存儲空間用f(n)表示。S(n)=O(f(n))，其中n為問題的規模，S(n)表示空間複雜度。
空間複雜度可以了解為除了原始序列大小的記憶體，在算法過程中用到的額外的存儲空間。
以二叉查找樹為例，舉例說明二叉排序樹的查找性能。
平衡二叉樹
如果二叉樹的是以紅黑樹等平衡二叉樹實作的，則 n 個節點的二叉排序樹的高度為 log2n+1 ，其查找效率為O(Log2n)，近似于折半查找。
清單二叉樹
如果二叉樹退變為清單了，則 n 個節點的高度或者說是長度變為了n，查找效率為O(n)，變成了順序查找。
一般二叉樹
介于「清單二叉樹」與「平衡二叉樹」之間，查找性能也在O(Log2n)到O(n)之間。
冰火交融
對于一個算法，其時間複雜度和空間複雜度往往是互相影響的。
比如說，要判斷某某年是不是閏年：
- 可以編寫一個算法來計算，這也就意味着，每次給一個年份，都是要通過計算得到是否是閏年的結果。
- 還有另一個辦法就是，事先建立一個有 5555 個元素的數組（年數比現實多就行），然後把所有的年份按下标的數字對應，如果是閏年，此數組項的值就是1，如果不是值為0。這樣，所謂的判斷某一年是否是閏年，就變成了查找這個數組的某一項的值是多少的問題。此時，我們的運算是最小化了，但是硬碟上或者記憶體中需要存儲這 5555 個 0 和 1 。
這就是典型的使用空間換時間的概念。
當追求一個較好的時間複雜度時，可能會使空間複雜度的性能變差，即可能導緻占用較多的存儲空間；
反之，求一個較好的空間複雜度時，可能會使時間複雜度的性能變差，即可能導緻占用較長的運作時間。
另外，算法的所有性能之間都存在着或多或少的互相影響。是以，當設計一個算法(特别是大型算法)時，要綜合考慮算法的各項性能，算法的使用頻率，算法處理的資料量的大小，算法描述語言的特性，算法運作的機器系統環境等各方面因素，才能夠設計出比較好的算法。
來源 | 五分鐘學算法
作者 | 程式員小吳