數據結構與算法 - 時間和空間復雜度

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

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)。

2 . 加法法則：總復雜度等于量級最大的那段代碼的復雜度

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

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)。

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

3 . 乘法法則：嵌套代碼的復雜度等于嵌套內外代碼復雜度的乘積

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

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(nn) = O(n2) 。

4 . 多個規模求加法：比如方法有兩個參數控制兩個循環的次數，那么這時就取二者復雜度相加

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)) 。

5 . 多個規模求乘法：比如方法有兩個參數控制兩個循環的次數，那么這時就取二者復雜度相乘

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(lognn) = O(nlogn) 。

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

包括 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) 是一個斐波那契數列[1]，通過歸納證明法可以證明，當 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) 這樣的對數階復雜度平時都用不到。