十分鐘弄懂：數據結構與算法之美 – 時間和空間複雜度

  • 2019 年 10 月 3 日
  • 筆記

複雜度分析是整個算法學習的精髓，只要掌握了它，數據結構和算法的內容基本上就掌握了一半了。

1. 什麼是複雜度分析 ？

  1. 數據結構和算法解決是 「如何讓計算機更快時間、更省空間的解決問題」。

  2. 因此需從執行時間和佔用空間兩個維度來評估數據結構和算法的性能。

  3. 分別用時間複雜度和空間複雜度兩個概念來描述性能問題，二者統稱為複雜度。

  4. 複雜度描述的是算法執行時間（或佔用空間）與數據規模的增長關係。

2. 為什麼要進行複雜度分析 ？

  1. 和性能測試相比，複雜度分析有不依賴執行環境、成本低、效率高、易操作、指導性強的特點。

  2. 掌握複雜度分析，將能編寫出性能更優的代碼，有利於降低系統開發和維護成本。

3. 如何進行複雜度分析 ？

3.1 大 O 表示法

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

3.2 時間複雜度

1）定義

算法的時間複雜度，也就是算法的時間量度。

大 O 時間複雜度表示法 實際上並不具體表示代碼真正的執行時間，而是表示 代碼執行時間隨數據規模增長的變化趨勢，所以也叫 漸進時間複雜度，簡稱 時間複雜度（asymptotic time complexity）。

例子1：

function aFun() {      console.log("Hello, World!");      //  需要執行 1 次      return 0;       // 需要執行 1 次  }

那麼這個方法需要執行 2 次運算。

例子 2：

function bFun(n) {      for(let i = 0; i < n; i++) {         // 需要執行 (n + 1) 次          console.log("Hello, World!");      // 需要執行 n 次      }      return 0;       // 需要執行 1 次  }

那麼這個方法需要執行 ( n + 1 + n + 1 ) = 2n +2 次運算。

例子 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 循環，所以第二層執行的是 n * n = n2 次，而且這裡的循環是 ++i，和例子 2 的是 i++，是不同的，是先加與後加的區別。

那麼這個方法需要執行 ( n2 + n2 + n + n + 1 + 1 +1 ) = 2n2 +2n + 3 。

2）特點

以時間複雜度為例，由於 時間複雜度 描述的是算法執行時間與數據規模的 增長變化趨勢，所以 常量、低階、係數 實際上對這種增長趨勢不產生決定性影響，所以在做時間複雜度分析時 忽略 這些項。

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

3.3 時間複雜度分析

    1. 只關注循環執行次數最多的一段代碼

單段代碼看高頻：比如循環。

function cal(n) {     let sum = 0;     let i = 1;     for (; i <= n; ++i) {       sum = sum + i;     }     return sum;   }

執行次數最多的是 for 循環及裏面的代碼，執行了 n 次，所以時間複雜度為 O(n)。

    1. 加法法則：總複雜度等於量級最大的那段代碼的複雜度

多段代碼取最大：比如一段代碼中有單循環和多重循環，那麼取多重循環的複雜度。

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 ，主要看循環部分。

第一部分，求 sum_1 ，明確知道執行了 100 次，而和 n 的規模無關，是個常量的執行時間，不能反映增長變化趨勢，所以時間複雜度為 O(1)。

第二和第三部分，求 sum_2 和 sum_3 ，時間複雜度是和 n 的規模有關的，為別為 O(n) 和 O(n2)。

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

同理類推，如果有 3 層 for 循環，那麼時間複雜度為 O(n3)，4 層就是 O(n4)。

所以，總的時間複雜度就等於量級最大的那段代碼的時間複雜度。

    1. 乘法法則：嵌套代碼的複雜度等於嵌套內外代碼複雜度的乘積

嵌套代碼求乘積：比如遞歸、多重循環等。

function cal(n) {     let ret = 0;     let i = 1;     for (; i < n; ++i) {       ret = ret + f(i); // 重點為  f(i)     }   }    function f(n) {    let sum = 0;    let i = 1;    for (; i < n; ++i) {      sum = sum + i;    }    return sum;   }

方法 cal 循環裏面調用 f 方法，而 f 方法裏面也有循環。

所以，整個 cal() 函數的時間複雜度就是，T(n) = T1(n) * T2(n) = O(n*n) = O(n2) 。

    1. 多個規模求加法：比如方法有兩個參數控制兩個循環的次數，那麼這時就取二者複雜度相加
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 的數據規模為 m、求 sum_2 的數據規模為 n，所以時間複雜度為 O(m+n)。

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

    1. 多個規模求乘法：比如方法有兩個參數控制兩個循環的次數，那麼這時就取二者複雜度相乘
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 循環 ，求 sum_3 的數據規模為 m 和 n，所以時間複雜度為 O(m*n)。

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

3.4 常用的時間複雜度分析

    1. 多項式階：隨着數據規模的增長，算法的執行時間和空間佔用，按照多項式的比例增長。

包括 O(1)（常數階）、O(logn)（對數階）、O(n)（線性階）、O(nlogn)（線性對數階）、O(n2) （平方階）、O(n3)（立方階）。

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

下面舉例說明 O(logn)（對數階）：

let i=1;  while (i <= n)  {     i = i * 2;  }

代碼是從 1 開始，每次循環就乘以 2，當大於 n 時，循環結束。

其實就是高中學過的等比數列，i 的取值就是一個等比數列。在數學裏面是這樣子的：

20 21 22 … 2k … 2x = n

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

實際上，不管是以 2 為底、以 3 為底，還是以 10 為底，我們可以把所有對數階的時間複雜度都記為 O(logn)。為什麼呢？

因為對數之間是可以互相轉換的，log3n = log32 * log2n，所以 O(log3n) = O(C * log2n)，其中 C=log32 是一個常量。

由於 時間複雜度 描述的是算法執行時間與數據規模的 增長變化趨勢，所以 常量、低階、係數 實際上對這種增長趨勢不產生決定性影響，所以在做時間複雜度分析時 忽略 這些項。

因此，在對數階時間複雜度的表示方法里，我們忽略對數的 「底」，統一表示為 O(logn)。

下面舉例說明 O(nlogn)（對數階）：

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 的時間複雜度為 O(logn)，而 cal 的時間複雜度為 O(n)，所以上面代碼的時間複雜度為 T(n) = T1(logn) * T2(n) = O(logn*n) = O(nlogn) 。

    1. 非多項式階：隨着數據規模的增長，算法的執行時間和空間佔用暴增，這類算法性能極差。

包括 O(2n)（指數階）、O(n!)（階乘階）。

O(2n)（指數階）例子：

aFunc( n ) {      if (n <= 1) {          return 1;      } else {          return aFunc(n - 1) + aFunc(n - 2);      }  }

參考答案：
顯然運行次數，T(0) = T(1) = 1，同時 T(n) = T(n – 1) + T(n – 2) + 1，這裡的 1 是其中的加法算一次執行。
顯然 T(n) = T(n – 1) + T(n – 2) 是一個斐波那契數列，通過歸納證明法可以證明，當 n >= 1 時 T(n) < (5/3)n，同時當 n > 4 時 T(n) >= (3/2)n。
所以該方法的時間複雜度可以表示為 O((5/3)n)，簡化後為 O(2n)。
可見這個方法所需的運行時間是以指數的速度增長的。
如果大家感興趣，可以試下分別用 1，10，100 的輸入大小來測試下算法的運行時間，相信大家會感受到時間複雜度的無窮魅力。

3.5 時間複雜度分類

時間複雜度可以分為：

  • 最好情況時間複雜度（best case time complexity）：在最理想的情況下，執行這段代碼的時間複雜度。
  • 最壞情況時間複雜度（worst case time complexity）：在最糟糕的情況下，執行這段代碼的時間複雜度。
  • 平均情況時間複雜度（average case time complexity），用代碼在所有情況下執行的次數的加權平均值表示。也叫 加權平均時間複雜度 或者 期望時間複雜度。
  • 均攤時間複雜度（amortized time complexity）: 在代碼執行的所有複雜度情況中絕大部分是低級別的複雜度，個別情況是高級別複雜度且發生具有時序關係時，可以將個別高級別複雜度均攤到低級別複雜度上。基本上均攤結果就等於低級別複雜度。

舉例說明：

// n 表示數組 array 的長度  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 函數實現的功能是在一個數組中找到值等於 x 的項，並返回索引值，如果沒找到就返回 -1 。

最好情況時間複雜度，最壞情況時間複雜度

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

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

平均情況時間複雜度

如何分析平均時間複雜度 ？代碼在不同情況下複雜度出現量級差別，則用代碼所有可能情況下執行次數的加權平均值表示。

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

省略掉係數、低階、常量，所以，這個公式簡化之後，得到的平均時間複雜度就是 O(n)。

我們知道，要查找的變量 x，要麼在數組裡，要麼就不在數組裡。這兩種情況對應的概率統計起來很麻煩，我們假設在數組中與不在數組中的概率都為 1/2。另外，要查找的數據出現在 0～n-1 這 n 個位置的概率也是一樣的，為 1/n。所以，根據概率乘法法則，要查找的數據出現在 0～n-1 中任意位置的概率就是 1/(2n)。

因此，前面的推導過程中存在的最大問題就是，沒有將各種情況發生的概率考慮進去。如果我們把每種情況發生的概率也考慮進去，那平均時間複雜度的計算過程就變成了這樣：

這個值就是概率論中的 加權平均值，也叫 期望值，所以平均時間複雜度的全稱應該叫 加權平均時間複雜度 或者 期望時間複雜度。

所以，根據上面結論推導出，得到的 平均時間複雜度 仍然是 O(n)。

均攤時間複雜度

均攤時間複雜度就是一種特殊的平均時間複雜度 (應用場景非常特殊，非常有限，這裡不說)。

3.6 時間複雜度總結

常用的時間複雜度所耗費的時間從小到大依次是：

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

常見的時間複雜度：

3.7 空間複雜度分析

時間複雜度的全稱是 漸進時間複雜度，表示 算法的執行時間與數據規模之間的增長關係 。

類比一下，空間複雜度全稱就是 漸進空間複雜度（asymptotic space complexity），表示 算法的存儲空間與數據規模之間的增長關係 。

定義：算法的空間複雜度通過計算算法所需的存儲空間實現，算法的空間複雜度的計算公式記作：S(n) = O(f(n))，其中，n 為問題的規模，f(n) 為語句關於 n 所佔存儲空間的函數。

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])    }  }

跟時間複雜度分析一樣，我們可以看到，第 2 行代碼中，我們申請了一個空間存儲變量 newArr ，是個空數組。第 3 行把 newArr 的長度修改為 n 的長度的數組，每項的值為 undefined ，除此之外，剩下的代碼都沒有佔用更多的空間，所以整段代碼的空間複雜度就是 O(n)。

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

4. 如何掌握好複雜度分析方法 ？

複雜度分析關鍵在於多練，所謂孰能生巧。

平時我們在寫代碼時，是用 空間換時間 還是 時間換空間，可以根據算法的時間複雜度和空間複雜度來衡量。

5. 最後

如果你覺得本文章或者項目對你有啟發，請給個贊或者 star 吧，點贊是一種美德，謝謝。

筆者文章常更地址：GitHub

參考文章：

複雜度分析（上）：如何分析、統計算法的執行效率和資源消耗？
(數據結構)十分鐘搞定算法時間複雜度

VirMach 便宜 VPS

QNews

QNews