十分鐘弄懂：數(shù)據(jù)結(jié)構(gòu)與算法之美 - 時(shí)間和空間復(fù)雜度

復(fù)雜度分析是整個(gè)算法學(xué)習(xí)的精髓，只要掌握了它，數(shù)據(jù)結(jié)構(gòu)和算法的內(nèi)容基本上就掌握了一半了。

1. 什么是復(fù)雜度分析 ？

*
數(shù)據(jù)結(jié)構(gòu)和算法解決是 “如何讓計(jì)算機(jī)更快時(shí)間、更省空間的解決問題”。

*
因此需從執(zhí)行時(shí)間和占用空間兩個(gè)維度來評(píng)估數(shù)據(jù)結(jié)構(gòu)和算法的性能。

*
分別用時(shí)間復(fù)雜度和空間復(fù)雜度兩個(gè)概念來描述性能問題，二者統(tǒng)稱為復(fù)雜度。

*
復(fù)雜度描述的是算法執(zhí)行時(shí)間（或占用空間）與數(shù)據(jù)規(guī)模的增長(zhǎng)關(guān)系。

2. 為什么要進(jìn)行復(fù)雜度分析 ？

*
和性能測(cè)試相比，復(fù)雜度分析有不依賴執(zhí)行環(huán)境、成本低、效率高、易操作、指導(dǎo)性強(qiáng)的特點(diǎn)。

*
掌握復(fù)雜度分析，將能編寫出性能更優(yōu)的代碼，有利于降低系統(tǒng)開發(fā)和維護(hù)成本。

3. 如何進(jìn)行復(fù)雜度分析 ？

3.1 大 O 表示法

算法的執(zhí)行時(shí)間與每行代碼的執(zhí)行次數(shù)成正比，用 T(n) = O(f(n)) 表示，其中 T(n) 表示算法執(zhí)行總時(shí)間，f(n) 表示每行代碼執(zhí)行總次數(shù)，而
n 往往表示數(shù)據(jù)的規(guī)模。這就是大 O 時(shí)間復(fù)雜度表示法。

3.2 時(shí)間復(fù)雜度

1）定義

算法的時(shí)間復(fù)雜度，也就是算法的時(shí)間量度。

大 O 時(shí)間復(fù)雜度表示法 實(shí)際上并不具體表示代碼真正的執(zhí)行時(shí)間，而是表示 代碼執(zhí)行時(shí)間隨數(shù)據(jù)規(guī)模增長(zhǎng)的變化趨勢(shì)，所以也叫 漸進(jìn)時(shí)間復(fù)雜度，簡(jiǎn)稱 時(shí)間復(fù)雜度
（asymptotic time complexity）。

例子1：
function aFun() { console.log("Hello, World!"); // 需要執(zhí)行 1 次 return 0; // 需要執(zhí)行
1 次 }
那么這個(gè)方法需要執(zhí)行 2 次運(yùn)算。

例子 2：
function bFun(n) { for(let i = 0; i < n; i++) { // 需要執(zhí)行 (n + 1) 次
console.log("Hello, World!"); // 需要執(zhí)行 n 次 } return 0; // 需要執(zhí)行 1 次 }
那么這個(gè)方法需要執(zhí)行 ( n + 1 + n + 1 ) = 2n +2 次運(yùn)算。

例子 3：
function cal(n) { let sum = 0; // 1 次 let i = 1; // 1 次 let j = 1; // 1 次 for
(; i <= n; ++i) { // n 次 j = 1; // n 次 for (; j <= n; ++j) { // n * n ，也即是 n平方次
sum = sum + i * j; // n * n ，也即是 n平方次 } } }
注意，這里是二層 for 循環(huán)，所以第二層執(zhí)行的是 n * n = n2 次，而且這里的循環(huán)是 ++i，和例子 2 的是
i++，是不同的，是先加與后加的區(qū)別。

那么這個(gè)方法需要執(zhí)行 ( n2 + n2 + n + n + 1 + 1 +1 ) = 2n2 +2n + 3 。

2）特點(diǎn)

以時(shí)間復(fù)雜度為例，由于 時(shí)間復(fù)雜度 描述的是算法執(zhí)行時(shí)間與數(shù)據(jù)規(guī)模的 增長(zhǎng)變化趨勢(shì)，所以 常量、低階、系數(shù)
實(shí)際上對(duì)這種增長(zhǎng)趨勢(shì)不產(chǎn)生決定性影響，所以在做時(shí)間復(fù)雜度分析時(shí)忽略 這些項(xiàng)。

所以，上面例子1 的時(shí)間復(fù)雜度為 T(n) = O(1)，例子2 的時(shí)間復(fù)雜度為 T(n) = O(n)，例子3 的時(shí)間復(fù)雜度為 T(n) = O(n2)。

3.3 時(shí)間復(fù)雜度分析

*
* 只關(guān)注循環(huán)執(zhí)行次數(shù)最多的一段代碼
單段代碼看高頻：比如循環(huán)。
function cal(n) { let sum = 0; let i = 1; for (; i <= n; ++i) { sum = sum + i;
} return sum; }
執(zhí)行次數(shù)最多的是 for 循環(huán)及里面的代碼，執(zhí)行了 n 次，所以時(shí)間復(fù)雜度為 O(n)。

*
* 加法法則：總復(fù)雜度等于量級(jí)最大的那段代碼的復(fù)雜度
多段代碼取最大：比如一段代碼中有單循環(huán)和多重循環(huán)，那么取多重循環(huán)的復(fù)雜度。
function cal(n) { let sum_1 = 0; let p = 1; for (; p < 100; ++p) { sum_1 =
sum_1 + p; } let sum_2 = 0; let q = 1; for (; q < n; ++q) { sum_2 = sum_2 + q;
} let sum_3 = 0; let i = 1; let j = 1; for (; i <= n; ++i) { j = 1; for (; j <=
n; ++j) { sum_3 = sum_3 + i * j; } } return sum_1 + sum_2 + sum_3; }
上面代碼分為三部分，分別求 sum_1、sum_2、sum_3 ，主要看循環(huán)部分。

第一部分，求 sum_1 ，明確知道執(zhí)行了 100 次，而和 n 的規(guī)模無(wú)關(guān)，是個(gè)常量的執(zhí)行時(shí)間，不能反映增長(zhǎng)變化趨勢(shì)，所以時(shí)間復(fù)雜度為 O(1)。

第二和第三部分，求 sum_2 和 sum_3 ，時(shí)間復(fù)雜度是和 n 的規(guī)模有關(guān)的，為別為 O(n) 和 O(n2)。

所以，取三段代碼的最大量級(jí)，上面例子的最終的時(shí)間復(fù)雜度為 O(n2)。

同理類推，如果有 3 層 for 循環(huán)，那么時(shí)間復(fù)雜度為 O(n3)，4 層就是 O(n4)。

所以，總的時(shí)間復(fù)雜度就等于量級(jí)最大的那段代碼的時(shí)間復(fù)雜度。

*
* 乘法法則：嵌套代碼的復(fù)雜度等于嵌套內(nèi)外代碼復(fù)雜度的乘積
嵌套代碼求乘積：比如遞歸、多重循環(huán)等。
function cal(n) { let ret = 0; let i = 1; for (; i < n; ++i) { ret = ret +
f(i); // 重點(diǎn)為 f(i) } } function f(n) { let sum = 0; let i = 1; for (; i < n;
++i) { sum = sum + i; } return sum; }
方法 cal 循環(huán)里面調(diào)用 f 方法，而 f 方法里面也有循環(huán)。

所以，整個(gè) cal() 函數(shù)的時(shí)間復(fù)雜度就是，T(n) = T1(n) * T2(n) = O(n*n) = O(n2) 。

*
* 多個(gè)規(guī)模求加法：比如方法有兩個(gè)參數(shù)控制兩個(gè)循環(huán)的次數(shù)，那么這時(shí)就取二者復(fù)雜度相加 function cal(m, n) { let sum_1 =
0; let i = 1; for (; i < m; ++i) { sum_1 = sum_1 + i; } let sum_2 = 0; let j =
1; for (; j < n; ++j) { sum_2 = sum_2 + j; } return sum_1 + sum_2; }
以上代碼也是求和 ，求 sum_1 的數(shù)據(jù)規(guī)模為 m、求 sum_2 的數(shù)據(jù)規(guī)模為 n，所以時(shí)間復(fù)雜度為 O(m+n)。

公式：T1(m) + T2(n) = O(f(m) + g(n)) 。

*
* 多個(gè)規(guī)模求乘法：比如方法有兩個(gè)參數(shù)控制兩個(gè)循環(huán)的次數(shù)，那么這時(shí)就取二者復(fù)雜度相乘 function cal(m, n) { let sum_3 =
0; let i = 1; let j = 1; for (; i <= m; ++i) { j = 1; for (; j <= n; ++j) {
sum_3 = sum_3 + i * j; } } }
以上代碼也是求和，兩層 for 循環(huán) ，求 sum_3 的數(shù)據(jù)規(guī)模為 m 和 n，所以時(shí)間復(fù)雜度為 O(m*n)。

公式：T1(m) * T2(n) = O(f(m) * g(n)) 。

3.4 常用的時(shí)間復(fù)雜度分析

*
* 多項(xiàng)式階：隨著數(shù)據(jù)規(guī)模的增長(zhǎng)，算法的執(zhí)行時(shí)間和空間占用，按照多項(xiàng)式的比例增長(zhǎng)。
包括 O(1)（常數(shù)階）、O(logn)（對(duì)數(shù)階）、O(n)（線性階）、O(nlogn)（線性對(duì)數(shù)階）、O(n2) （平方階）、O(n3)（立方階）。

除了 O(logn)、O(nlogn) ，其他的都可從上面的幾個(gè)例子中看到。

下面舉例說明 O(logn)（對(duì)數(shù)階）：
let i=1; while (i <= n) { i = i * 2; }
代碼是從 1 開始，每次循環(huán)就乘以 2，當(dāng)大于 n 時(shí)，循環(huán)結(jié)束。

其實(shí)就是高中學(xué)過的等比數(shù)列，i 的取值就是一個(gè)等比數(shù)列。在數(shù)學(xué)里面是這樣子的：

20 21 22 ... 2k ... 2x = n

所以，我們只要知道 x 值是多少，就知道這行代碼執(zhí)行的次數(shù)了，通過 2x = n 求解 x，數(shù)學(xué)中求解得 x = log2n 。所以上面代碼的時(shí)間復(fù)雜度為
O(log2n)。

實(shí)際上，不管是以 2 為底、以 3 為底，還是以 10 為底，我們可以把所有對(duì)數(shù)階的時(shí)間復(fù)雜度都記為 O(logn)。為什么呢？

因?yàn)閷?duì)數(shù)之間是可以互相轉(zhuǎn)換的，log3n = log32 * log2n，所以 O(log3n) = O(C * log2n)，其中 C=log32
是一個(gè)常量。

由于 時(shí)間復(fù)雜度 描述的是算法執(zhí)行時(shí)間與數(shù)據(jù)規(guī)模的 增長(zhǎng)變化趨勢(shì)，所以 常量、低階、系數(shù) 實(shí)際上對(duì)這種增長(zhǎng)趨勢(shì)不產(chǎn)生決定性影響，所以在做時(shí)間復(fù)雜度分析時(shí) 忽略
這些項(xiàng)。

因此，在對(duì)數(shù)階時(shí)間復(fù)雜度的表示方法里，我們忽略對(duì)數(shù)的 “底”，統(tǒng)一表示為 O(logn)。

下面舉例說明 O(nlogn)（對(duì)數(shù)階）：
function aFun(n){ let i = 1; while (i <= n) { i = i * 2; } return i } function
cal(n) { let sum = 0; for (let i = 1; i <= n; ++i) { sum = sum + aFun(n); }
return sum; }
aFun 的時(shí)間復(fù)雜度為 O(logn)，而 cal 的時(shí)間復(fù)雜度為 O(n)，所以上面代碼的時(shí)間復(fù)雜度為 T(n) = T1(logn) * T2(n)
= O(logn*n) = O(nlogn) 。

*
* 非多項(xiàng)式階：隨著數(shù)據(jù)規(guī)模的增長(zhǎng)，算法的執(zhí)行時(shí)間和空間占用暴增，這類算法性能極差。
包括 O(2n)（指數(shù)階）、O(n!)（階乘階）。

O(2n)（指數(shù)階）例子：
aFunc( n ) { if (n <= 1) { return 1; } else { return aFunc(n - 1) + aFunc(n -
2); } }
參考答案：
顯然運(yùn)行次數(shù)，T(0) = T(1) = 1，同時(shí) T(n) = T(n - 1) + T(n - 2) + 1，這里的 1 是其中的加法算一次執(zhí)行。
顯然 T(n) = T(n - 1) + T(n - 2) 是一個(gè)斐波那契數(shù)列
<https://baike.baidu.com/item/%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0%E5%88%97>
，通過歸納證明法可以證明，當(dāng) n >= 1 時(shí) T(n) < (5/3)n，同時(shí)當(dāng) n > 4 時(shí) T(n) >= (3/2)n。
所以該方法的時(shí)間復(fù)雜度可以表示為 O((5/3)n)，簡(jiǎn)化后為 O(2n)。
可見這個(gè)方法所需的運(yùn)行時(shí)間是以指數(shù)的速度增長(zhǎng)的。
如果大家感興趣，可以試下分別用 1，10，100 的輸入大小來測(cè)試下算法的運(yùn)行時(shí)間，相信大家會(huì)感受到時(shí)間復(fù)雜度的無(wú)窮魅力。

3.5 時(shí)間復(fù)雜度分類

時(shí)間復(fù)雜度可以分為：

* 最好情況時(shí)間復(fù)雜度（best case time complexity）：在最理想的情況下，執(zhí)行這段代碼的時(shí)間復(fù)雜度。
* 最壞情況時(shí)間復(fù)雜度（worst case time complexity）：在最糟糕的情況下，執(zhí)行這段代碼的時(shí)間復(fù)雜度。
* 平均情況時(shí)間復(fù)雜度（average case time complexity），用代碼在所有情況下執(zhí)行的次數(shù)的加權(quán)平均值表示。也叫 加權(quán)平均時(shí)間復(fù)雜度
或者期望時(shí)間復(fù)雜度。
* 均攤時(shí)間復(fù)雜度（amortized time complexity）:
在代碼執(zhí)行的所有復(fù)雜度情況中絕大部分是低級(jí)別的復(fù)雜度，個(gè)別情況是高級(jí)別復(fù)雜度且發(fā)生具有時(shí)序關(guān)系時(shí)，可以將個(gè)別高級(jí)別復(fù)雜度均攤到低級(jí)別復(fù)雜度上?；旧暇鶖偨Y(jié)果就等于低級(jí)別復(fù)雜度。
舉例說明：
// n 表示數(shù)組 array 的長(zhǎng)度 function find(array, n, x) { let i = 0; let pos = -1; for
(; i < n; ++i) { if (array[i] == x) { pos = i; break; } } return pos; }
find 函數(shù)實(shí)現(xiàn)的功能是在一個(gè)數(shù)組中找到值等于 x 的項(xiàng)，并返回索引值，如果沒找到就返回 -1 。

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

如果數(shù)組中第一個(gè)值就等于 x，那么時(shí)間復(fù)雜度為 O(1)，如果數(shù)組中不存在變量 x，那我們就需要把整個(gè)數(shù)組都遍歷一遍，時(shí)間復(fù)雜度就成了
O(n)。所以，不同的情況下，這段代碼的時(shí)間復(fù)雜度是不一樣的。

所以上面代碼的 最好情況時(shí)間復(fù)雜度為 O(1)，最壞情況時(shí)間復(fù)雜度為 O(n)。

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

如何分析平均時(shí)間復(fù)雜度 ？代碼在不同情況下復(fù)雜度出現(xiàn)量級(jí)差別，則用代碼所有可能情況下執(zhí)行次數(shù)的加權(quán)平均值表示。

要查找的變量 x 在數(shù)組中的位置，有 n+1 種情況：在數(shù)組的 0～n-1 位置中和不在數(shù)組中。我們把每種情況下，查找需要遍歷的元素個(gè)數(shù)累加起來，然后再除以
n+1，就可以得到需要遍歷的元素個(gè)數(shù)的平均值，即：



省略掉系數(shù)、低階、常量，所以，這個(gè)公式簡(jiǎn)化之后，得到的平均時(shí)間復(fù)雜度就是 O(n)。

我們知道，要查找的變量 x，要么在數(shù)組里，要么就不在數(shù)組里。這兩種情況對(duì)應(yīng)的概率統(tǒng)計(jì)起來很麻煩，我們假設(shè)在數(shù)組中與不在數(shù)組中的概率都為
1/2。另外，要查找的數(shù)據(jù)出現(xiàn)在 0～n-1 這 n 個(gè)位置的概率也是一樣的，為 1/n。所以，根據(jù)概率乘法法則，要查找的數(shù)據(jù)出現(xiàn)在 0～n-1
中任意位置的概率就是 1/(2n)。

因此，前面的推導(dǎo)過程中存在的最大問題就是，沒有將各種情況發(fā)生的概率考慮進(jìn)去。如果我們把每種情況發(fā)生的概率也考慮進(jìn)去，那平均時(shí)間復(fù)雜度的計(jì)算過程就變成了這樣：



這個(gè)值就是概率論中的 加權(quán)平均值，也叫 期望值，所以平均時(shí)間復(fù)雜度的全稱應(yīng)該叫 加權(quán)平均時(shí)間復(fù)雜度 或者 期望時(shí)間復(fù)雜度。

所以，根據(jù)上面結(jié)論推導(dǎo)出，得到的 平均時(shí)間復(fù)雜度 仍然是 O(n)。

均攤時(shí)間復(fù)雜度

均攤時(shí)間復(fù)雜度就是一種特殊的平均時(shí)間復(fù)雜度 (應(yīng)用場(chǎng)景非常特殊，非常有限，這里不說)。

3.6 時(shí)間復(fù)雜度總結(jié)

常用的時(shí)間復(fù)雜度所耗費(fèi)的時(shí)間從小到大依次是：

O(1) < O(logn) < (n) < O(nlogn) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn)

常見的時(shí)間復(fù)雜度：









3.7 空間復(fù)雜度分析

時(shí)間復(fù)雜度的全稱是 漸進(jìn)時(shí)間復(fù)雜度，表示 算法的執(zhí)行時(shí)間與數(shù)據(jù)規(guī)模之間的增長(zhǎng)關(guān)系 。

類比一下，空間復(fù)雜度全稱就是 漸進(jìn)空間復(fù)雜度（asymptotic space complexity），表示 算法的存儲(chǔ)空間與數(shù)據(jù)規(guī)模之間的增長(zhǎng)關(guān)系 。

定義：算法的空間復(fù)雜度通過計(jì)算算法所需的存儲(chǔ)空間實(shí)現(xiàn)，算法的空間復(fù)雜度的計(jì)算公式記作：S(n) = O(f(n))，其中，n 為問題的規(guī)模，f(n)
為語(yǔ)句關(guān)于 n 所占存儲(chǔ)空間的函數(shù)。
function print(n) { const newArr = []; // 第 2 行 newArr.length = n; // 第 3 行
for (let i = 0; i <n; ++i) { newArr[i] = i * i; } for (let j = n-1; j >= 0;
--j) { console.log(newArr[i]) } }
跟時(shí)間復(fù)雜度分析一樣，我們可以看到，第 2 行代碼中，我們申請(qǐng)了一個(gè)空間存儲(chǔ)變量 newArr ，是個(gè)空數(shù)組。第 3 行把 newArr 的長(zhǎng)度修改為 n
的長(zhǎng)度的數(shù)組，每項(xiàng)的值為 undefined ，除此之外，剩下的代碼都沒有占用更多的空間，所以整段代碼的空間復(fù)雜度就是 O(n)。

我們常見的空間復(fù)雜度就是 O(1)、O(n)、O(n2)，像 O(logn)、O(nlogn) 這樣的對(duì)數(shù)階復(fù)雜度平時(shí)都用不到。

4. 如何掌握好復(fù)雜度分析方法 ？

復(fù)雜度分析關(guān)鍵在于多練，所謂孰能生巧。

平時(shí)我們?cè)趯懘a時(shí)，是用 空間換時(shí)間 還是 時(shí)間換空間，可以根據(jù)算法的時(shí)間復(fù)雜度和空間復(fù)雜度來衡量。

5. 最后

如果你覺得本文章或者項(xiàng)目對(duì)你有啟發(fā)，請(qǐng)給個(gè)贊或者 star 吧，點(diǎn)贊是一種美德，謝謝。

筆者文章常更地址：GitHub <https://github.com/biaochenxuying/blog>

參考文章：

復(fù)雜度分析（上）：如何分析、統(tǒng)計(jì)算法的執(zhí)行效率和資源消耗？ <https://time.geekbang.org/column/article/40036>
(數(shù)據(jù)結(jié)構(gòu))十分鐘搞定算法時(shí)間復(fù)雜度 <https://www.jianshu.com/p/f4cca5ce055a>

• ? 上一篇： [基礎(chǔ)篇]ESP8266-SDK教程(零)之認(rèn)識(shí)并了解
• ? 下一篇：C# 表達(dá)式樹Lambda擴(kuò)展（四）