• 本文已收錄于專欄《資料結構入門》

🙉飯不食，水不飲，題必須刷🙉
C語言免費動漫教程，和我一起打卡！ 🌞《光天化日學C語言》🌞
LeetCode 太難？先看簡單題！ 🧡《C語言入門100例》🧡
資料結構難？不存在的！ 🌳《資料結構入門》🌳
LeetCode 太簡單？演算法學起來！ 🌌《夜深人靜寫演算法》🌌
究極演算法奧義！深度學習！ 🟣《深度學習100例》🟣

政治

一、前言

??「資料結構」 和 「演算法」 是密不可分的，兩者往往是相輔相成的，所以，在學習 「資料結構」 的程序中，不免會遇到各種「演算法」，
??零基礎學演算法的最好方法，莫過于刷題了，當然，刷題是不夠的，刷的程序中也要多多總結，多多思考，養成 「經常思考」 的習慣，這就是所謂的 「 流水不腐，戶樞不蠹 」，任何事情都是需要堅持的，刷題也一樣，沒有刷夠足夠的題，就很難做出系統性的總結，所以上大學的時候，我花了三年的時間來刷題， 作業以后還是會抽點時間出來刷題，
??千萬不要用作業忙來找借口，時間擠一擠總是有的，
??很多人覺得演算法難，是因為被困在了時間和空間這兩個維度上，如果不考慮時間和空間的因素，其實我們可以把所有問題都通過「窮舉法」 來解決，也就是你告訴計算機你要做什么，然后通過它強大的算力幫你計算，
??那么，說到了時間，今天我就和大家來聊一下 「 演算法時間復雜度 」，

二、窮舉法

1、單層回圈

• 所謂窮舉法，就是我們通常所說的列舉，就是把所有情況都遍歷了（跑到）的意思，舉個最簡單的例子：

【例題1】給定 n ( n ≤ 1000 ) n(n \le 1000) n(n≤1000) 個元素 a i a_i ai?，求其中 奇數 有多少個，

• 判斷一個數是偶數還是奇數，只需要求它除上 2 的余數是 0 還是 1，那么我們把所有數都判斷一遍，并且對符合條件的情況進行計數，最后回傳這個計數器就是答案，這里需要遍歷所有的數，這就是窮舉，如圖二-1-1所示：
  圖二-1-1
• c/c++ 代碼實作如下：

int countOdd(int n, int a[]) {
    int cnt = 0;
    for(int i = 0; i < n; ++i) {
        if(a[i] & 1)
            ++cnt;
    }
    return cnt;
}

• 其中a & 1等價于a % 2，代碼a模 2 的余數；
• 具體原因可以參見位與運算子的用法：??光天化日學C語言??（14）- 位運算 & 的應用，

2、雙層回圈

• 經過上面的例子，相信你對窮舉法已經有一定的理解，那么我們來看看稍微復雜一點的情況，

【例題2】給定 n ( n ≤ 1000 ) n(n \le 1000) n(n≤1000) 個元素 a i a_i ai?，求有多少個二元組 ( i , j ) (i,j) (i,j)，滿足 a i + a j a_i + a_j ai?+aj? 是奇數 ( i < j ) (i \lt j) (i<j)，

• 我們還是秉承窮舉法的思想，這里需要兩個變數 i i i 和 j j j，所以可以列舉 a i a_i ai? 和 a j a_j aj?，再對 a i + a j a_i + a_j ai?+aj? 進行奇偶性判斷，所以很快設計出一個利用窮舉的演算法，如圖二-2-1所示：
  圖二-2-1
• c/c++ 代碼實作如下：

int countOddPair(int n, int a[]) {
    int cnt = 0;
    for(i = 0; i < n; ++i) {
        for(j = i+1; j < n; ++j) {
            if( (a[i] + a[j]) & 1)
                ++cnt;
        }
    }
    return cnt;
}

3、三層回圈

• 經過這兩個例子，是不是對窮舉已經有點感覺了？那么，我們繼續來看下一個例子，

【例題3】給定 n ( n ≤ 1000 ) n(n \le 1000) n(n≤1000) 個元素 a i a_i ai?，求有多少個三元組 ( i , j , k ) (i,j,k) (i,j,k)，滿足 a i + a j + a k a_i + a_j + a_k ai?+aj?+ak? 是奇數 ( i < j < k ) (i \lt j \lt k) (i<j<k)，

• 相信聰明的你也已經猜到了，直接給出代碼：

int countOddTriple(int n, int a[]) {
    int cnt = 0;
    for(i = 0; i < n; ++i) {
        for(j = i+1; j < n; ++j) {
            for(int k = j+1; k < n; ++k) {
                if( (a[i] + a[j] + a[k]) & 1 )
                    ++cnt;
            }
        }
    }
    return cnt;
}

• 這時候，相信聰明的你，已經意識到一個問題；
• 它就是：
  
• 是的，隨著回圈嵌套的增多，時間消耗會越來越多，并且是三個回圈是乘法的關系，也就是遍歷次數隨著 n n n 的增加，呈立方式的增長，

4、遞回列舉

??【例題4】給定 n ( n ≤ 1000 ) n(n \le 1000) n(n≤1000) 個元素 a i a_i ai? 和一個整數 k ( k ≤ n ) k (k \le n) k(k≤n)，求有多少個有序 k k k 元組，滿足 它們的和 是偶數，

• 一層回圈，兩層回圈，三層回圈， k k k 層回圈？
• 我們需要根據 k k k 的不同，決定寫幾層回圈， k k k 的最大值為 1000，也就意味著我們要寫 1000 的 if else 陳述句，
• 顯然，這樣是無法接受，比較暴力的做法是采用到遞回；
• c/c++ 代碼實作如下：

int dfs(int n, int a[], int start, int k, int sum) {
    if(k == 0)
        return (sum & 1) ? 0 : 1;             // (1)
    int s = 0; 
    for(int i = start; i < n; ++i)
        s += dfs(n, a, i+1, k-1, sum + a[i]); // (2)
    return s;
}

• 這是一個經典的深度優先遍歷的程序，對于初學者來說可能比較難理解，這個程序比較復雜，我來簡單解釋一下，
  

• ( 1 ) (1) (1) dfs(int n, int a[], int start, int k, int sum)這個函式的含義是：給定 n n n 元素的陣列 a [ ] a[] a[]，從下標 s t a r t start start 開始，選擇 k k k 個元素，得到的和為 s u m sum sum 的情況下的方案數，當 k = 0 k=0 k=0 時代表的是遞回的出口；

• ( 2 ) (2) (2) 當前第 i i i 元素選擇以后，剩下就是從 i + 1 i+1 i+1 個元素開始選擇 k ? 1 k-1 k?1 個的情況，遞回求解，

• 我們簡單分析一下， n n n 個元素選擇 k k k 個，根據排列組合，方案數為： C n k C_n^k Cnk?，當 n = 1000 ， k = 500 n=1000，k=500 n=1000，k=500 時已經是天文數字，這段代碼是完全出不了解的，

• 當然，對于初學者來說，這段代碼如果不理解，問題也不大，只是為了說明窮舉這個思想，

三、時間復雜度

1、時間復雜度的表示法

??在進行演算法分析時，陳述句總的執行次數 T ( n ) T(n) T(n) 是關于問題規模 n n n 的函式，進而分析 T ( n ) T(n) T(n) 隨著 n n n 的變化情況而確定 T ( n ) T(n) T(n) 的數量級，
??演算法的時間復雜度，就是演算法的時間度量，記作： T ( n ) = O ( f ( n ) ) T(n) = O(f(n)) T(n)=O(f(n)) 用大寫的 O 來體現演算法時間復雜度的記法，我們稱之為 大 O 記法，

1、時間函式

時間復雜度往往會聯系到一個函式，自變數 表示規模，應變數 表示執行時間，

• 這里所說的執行時間，是指廣義的時間，也就是單位并不是 “秒”、“毫秒” 這些時間單位，它代表的是一個 “執行次數” 的概念，我們用 f ( n ) f(n) f(n) 來表示這個時間函式，

2、經典函式舉例

• 在【例題1】中，我們接觸到了單層回圈，這里的 n n n 是一個變數，隨著 n n n 的增大，執行次數增大，執行時間就會增加，所以就有了時間函式的表示法如下：
• f ( n ) = n f(n) = n f(n)=n
  圖三-2-1
• 這個就是最經典的線性時間函式，
• 在【例題2】中，我們接觸到了雙層回圈，它的時間函式表示法如下：
• f ( n ) = n ( n ? 1 ) 2 f(n) = \frac {n(n-1)} 2 f(n)=2n(n?1)?
  圖三-2-2
• 這是一個平方級別的時間函式，
• 在【例3】中，我們接觸到了三層回圈，它的時間函式表示法如下：
• f ( n ) = n ( n ? 1 ) ( n ? 2 ) 6 f(n) = \frac {n(n-1)(n-2)} 6 f(n)=6n(n?1)(n?2)?
  圖三-2-3
• 這是一個立方級別的時間函式，

3、時間復雜度

• 一個演算法中的陳述句執行次數稱為陳述句頻度或時間頻度，記為 T ( n ) T(n) T(n)，
• 并且我們有一個更加優雅的表示法，即：
• T ( n ) = O ( f ( n ) ) T(n) = O(f(n)) T(n)=O(f(n))
• 其中 O O O 念成 “大O”；
• 1）當 f ( n ) = n f(n) = n f(n)=n，我們稱這個演算法擁有線性時間復雜度，記作 O ( n ) O(n) O(n)；
• 2）當 f ( n ) = n ( n ? 1 ) 2 f(n) = \frac {n(n-1)} 2 f(n)=2n(n?1)?，我們稱這個演算法擁有平方級時間復雜度，記作 O ( n 2 ) O(n^2) O(n2)；
• 3）當 f ( n ) = n ( n ? 1 ) ( n ? 2 ) 6 f(n) = \frac {n(n-1)(n-2)} 6 f(n)=6n(n?1)(n?2)?, 我們稱這個演算法擁有立方級的時間復雜度，記作 O ( n 3 ) O(n^3) O(n3)；
• 這時候我們發現， f f f 的函式可能很復雜，但是 O O O 表示的函式往往比較簡單，它舍棄了一些 “細節” ，這是為什么呢？
• 接下來我們來談下數學上一個非常有名的概念 “高階無窮小”，

4、高階無窮小

• 有這么一個定義：如果 l i m ( β / α ) = 0 lim(β / α) = 0 lim(β/α)=0，則稱“ β β β 是比 α α α 較高階的無窮小”，

• 如果對極限沒有什么概念，我會用更加通俗的語言來解釋一下，

• 我們來看上面提到的一個函式：

• f ( n ) = n ( n ? 1 ) 2 = 1 2 n 2 ? 1 2 n f(n) = \frac {n(n-1)} 2 = \frac 1 2 n^2 - \frac 1 2 n f(n)=2n(n?1)?=21?n2?21?n

• 總共兩部分組成：一部分是 n 2 n^2 n2 的部分，另一部分是 n n n 的部分，直觀感受，那個更大呢？
  

• 顯而易見，一定是 n 2 n^2 n2，相對于 n 2 n^2 n2 來說， n n n 就是 “小巫見大巫” ！

• 所以隨著 n n n 的增長，線性的部分增長已經跟不上平方部分，這樣，線性部分的時間消耗相對于平方不分來說已經 “微不足道”，所以我們就索性不提它了，于是就有時間復雜度表示如下：

• T ( n ) = O ( f ( n ) ) = O ( 1 2 n 2 ? 1 2 n ) = O ( 1 2 n 2 ) = O ( n 2 ) \begin{aligned} T(n) &= O(f(n)) \\ &= O(\frac 1 2 n^2 - \frac 1 2 n) \\ &= O(\frac 1 2 n^2) \\ &= O(n^2)\end{aligned} T(n)?=O(f(n))=O(21?n2?21?n)=O(21?n2)=O(n2)?

• 所以它的時間復雜度就是 O ( n ) O(n) O(n) 了，

5、簡化系數

• 我們發現上述的公式推導的程序中，將 n 2 n^2 n2 前面的系數 1 2 \frac 1 2 21? 給去掉了，這是由于 時間復雜度描述的更多的是一個數量級，所以盡量減少干擾項，對于兩個不同的問題，可能執行時間不同，但是我們可以說他們的 時間復雜度 是一樣的，
• 接下來讓我們來看下一些常見的時間復雜度，

四、常見的時間復雜度

1、常數階

const int MAXN = 1024;
int getMAXN() {
	return MAXN;
}

• 這個比較好理解，一共就一句話，沒有回圈，是常數時間，表示為 O ( 1 ) O(1) O(1)，

2、對數階

【例題4】給定 n ( n ≤ 100000 ) n(n \le 100000) n(n≤100000) 個元素的有序陣列 a i a_i ai? 和 整數 v v v，求 v v v 在陣列中的下標，不存在輸出 -1，

• 這個問題就是一個常見的查詢問題，我們可以用 O ( n ) O(n) O(n) 的演算法遍歷整個陣列，然后去找 v v v 的值，
• 當然，也有更快的辦法，注意到題目中的條件，陣列 a i a_i ai? 是有序的，所以我們可以利用二分查找來實作，

int bin(int n, int a[], int v) {
	int l = 0, r = n - 1;
	while(l <= r) {
		mid = (l + r) >> 1;
		if(a[mid] == v) 
		    return mid;
		else if(a[mid] < v)
			r = mid + 1;
		else
			l = mid + 1;
	}
	return -1;
}

• 這是一個二分查找的實作，時間復雜度為 O ( l o g 2 n ) O(log_2n) O(log2?n)，
• 每次相當于把 n n n 切半，即：
• n → n 2 → n 4 → . . . → n 2 k → . . . → 0 n \to \frac n 2 \to \frac n 4 \to ...\to \frac n {2^k} \to ... \to 0 n→2n?→4n?→...→2kn?→...→0
• 這條路徑的長度也就是執行次數，也就是要求 2 k ≤ n 2^k \le n 2k≤n 中的 k k k 的最大值，兩邊取以2為底的對數，得到：
• k ≤ l o g 2 n k \le log_2n k≤log2?n
• 所以 T ( n ) = O ( f ( n ) ) = O ( k ) = O ( l o g 2 n ) T(n) = O(f(n)) = O(k) = O(log_2n) T(n)=O(f(n))=O(k)=O(log2?n)，

3、根號階

【例題5】給定一個數 n ( n ≤ 1 0 9 ) n(n \le 10^9) n(n≤109)，問 n n n 是否是一個素數（素數的概念，就是除了1和它本身，沒有其它因子），

• 基于素數的概念，我們可以列舉所有 i ∈ [ 2 , n ) i \in [2, n) i∈[2,n)，看能否整除 n n n，一旦能整除，代表找到了一個因子，則不是素數；當所有數列舉完還沒找到，它就是素數，
• 但是這樣做，顯然效率太低，所以我們需要進行一些思考，最后得到以下演算法：

bool isPrime(int n) {
    int i;
    int sqrtn = sqrt(n + 0.0);
    for(int i = 2; i <= sqrtn; ++i) {
        if(n % i == 0) {
            return false;
        }
    }
    return true;
}

• 這個演算法的時間復雜度為 O ( n ) O(\sqrt n) O(n ?)，
• 為什么只需要列舉 n \sqrt n n ? 內的數呢？
• 因為一旦有一個因子 s s s，必然有另一個因子 n s \frac n s sn?，它們之間必然有個大小關系，無論是 s ≤ n s s \le \frac n s s≤sn? 還是 n s ≤ s \frac n s \le s sn?≤s，都能通過兩邊乘上 s s s 得出：
• s ≤ n s \le \sqrt n s≤n ?

4、線性階

• 【例題1】中我們接觸到的單層回圈，這里的 n n n 是一個變數，隨著 n n n 的增大，執行次數增大，執行時間就會增加，所以就有了時間函式的表示法如下：
• f ( n ) = n f(n) = n f(n)=n
  
• 這個就是最經典的線性時間，即 O ( n ) O(n) O(n)，

5、線性對數階

【例題6】給定 n ( n ≤ 100000 ) n(n \le 100000) n(n≤100000) 個元素 a i a_i ai?，求滿足 a i + a j = 1024 a_i + a_j = 1024 ai?+aj?=1024 的有序二元組 ( i , j ) (i,j) (i,j) 有多少對，

• 首先，還是先思考最樸素的演算法，當然是兩層列舉了，參考【例題2】，時間復雜度 O ( n 2 ) O(n^2) O(n2)，
• 但是，這個問題 n n n 的范圍較大，
• 我們來看下這個問題，如果你對 【例題4】已經理解了，那么這個問題也就不難了，
• 我們可以先對所有元素 a i a_i ai? 按照遞增排序，然后列舉 a i a_i ai?，并且在 [ i + 1 , n ) [i+1, n) [i+1,n) 范圍內找是否存在 a j = 1024 ? a i a_j = 1024 - a_i aj?=1024?ai?，存在則計數器 + 1，而這個找的程序可以采用二分列舉，所以時間復雜度就是： O ( n l o g 2 n ) O(nlog_2n) O(nlog2?n)，

6、多項式階

• 多項式的含義是函式 f ( n ) f(n) f(n) 可以表示成如下形式：
• f ( n ) = a n k + b n k ? 1 + . . . + C f(n) = an^k + bn^{k-1} + ... + C f(n)=ank+bnk?1+...+C
• 所以 O ( n 5 ) O(n^5) O(n5)、 O ( n 4 ) O(n^4) O(n4)、 O ( n 3 ) O(n^3) O(n3)（立方階）、 O ( n 2 ) O(n^2) O(n2)（平方階）、 O ( n ) O(n) O(n)（線性階） 都是多項式時間，

7、指數階

【例題7】給出 n ( n ≤ 15 ) n(n \le 15) n(n≤15) 個點，以及每兩個點之間的關系（連通還是不連通），求一個最大的集合，使得在這個集合中都連通，

• 這是求子集的問題，由于最多只有 15 15 15 個點，我們就可以列舉每個點選或者不選，總共 2 n 2^n 2n 種情況，然后再判斷是否滿足題目中的連通性，這個演算法時間復雜度為 O ( n 2 2 n ) O(n^22^n) O(n22n)；
• 當然有更加優秀的演算法，但不是本文討論的重點，所以就交給優秀的你自己去探索啦！

8、階乘階

【例題8】給定 n ( n ≤ 12 ) n(n \le 12) n(n≤12) 個點，并且給出任意兩點間的距離，求從 s s s 點開始經過所有點回到 s s s 的距離的最小值，

• 這個問題就是典型的暴力列舉所有情況求解，可以把這些點當成是一個排列，所以排列方案數為 n ! n! n!，
• 暴力列舉的時間復雜度為 O ( n ! ) O(n!) O(n!)，
• 當然，一般這類問題，暴力搜索沒有實際意義，我們可以通過動態規劃來進行優化，

五、如何判斷時間復雜度

• 接下來我們來討論下，如何通過一個問題的規模來判斷這個問題應該能夠承受的時間復雜度，

1、標準

• 首先，我們需要一個標準，也就是總執行次數多少合適，
• 這個標準是我經過多年做題經驗得出，我們把它定義為 S = 1 0 6 S = 10^6 S=106，

2、問題規模

• 有了標準以后，我們還需要知道問題規模，也就是 O ( n ) O(n) O(n) 中的 n n n，

3、套公式

• 然后就是憑感覺套公式了，
• 當 n < 12 n < 12 n<12 時，可能是需要用到階乘級別的演算法，即 O ( n ! ) O(n!) O(n!)；
• 當 n < 16 n < 16 n<16 時，可能是需要狀態壓縮的演算法，比如 O ( 2 n ) O(2^n) O(2n)、 O ( n 2 n ) O(n2^n) O(n2n)、 O ( n 2 2 n ) O(n^22^n) O(n22n)；
• 當 n < 30 n < 30 n<30 時，可能是需要 O ( n 4 ) O(n^4) O(n4) 的演算法，因為 3 0 4 30^4 304 差不多接近 1 0 6 10^6 106；
• 當 n < 100 n < 100 n<100 時，可能是需要 O ( n 3 ) O(n^3) O(n3) 的演算法，因為 10 0 3 = 1 0 6 100^3 = 10^6 1003=106；
• 當 n < 1000 n < 1000 n<1000 時，可能是需要 O ( n 2 ) O(n^2) O(n2) 的演算法，因為 100 0 2 = 1 0 6 1000^2 = 10^6 10002=106；
• 當 n < 100000 n < 100000 n<100000 時，可能是需要 O ( n l o g 2 n ) O(nlog_2n) O(nlog2?n)、 O ( n ( l o g 2 n ) 2 ) O(n(log_2n)^2) O(n(log2?n)2) 的演算法；
• 當 n < 1000000 n < 1000000 n<1000000 時，可能是需要 O ( n ) O(\sqrt n) O(n ?)、 O ( n ) O(n) O(n) 的演算法；
• 細心的讀者可能會發現，我在描述的時候都是用了可能的語氣，那是因為以上資料量都是我通過做題總結出來的，有時候還需要結合題目本身的時間限制、出題人的陰險程度 來決定，所以不能一概而論，

六、演算法長文推薦

• 《演算法全套路線學習》
• 《演算法刷題啟示錄》

作者其他專欄：

🙉飯不食，水不飲，題必須刷🙉
C語言免費動漫教程，和我一起打卡！ 🌞《光天化日學C語言》🌞
LeetCode 太難？先看簡單題！ 🧡《C語言入門100例》🧡
資料結構難？不存在的！ 🌳《資料結構入門》🌳
LeetCode 太簡單？演算法學起來！ 🌌《夜深人靜寫演算法》🌌
究極演算法奧義！深度學習！ 🟣《深度學習100例》🟣