摘要：什么是復(fù)雜度分析數(shù)據(jù)結(jié)構(gòu)和算法解決是如何讓計(jì)算機(jī)更快時(shí)間更省空間的解決問題。分別用時(shí)間復(fù)雜度和空間復(fù)雜度兩個(gè)概念來描述性能問題，二者統(tǒng)稱為復(fù)雜度。復(fù)雜度描述的是算法執(zhí)行時(shí)間或占用空間與數(shù)據(jù)規(guī)模的增長(zhǎng)關(guān)系。這就是大時(shí)間復(fù)雜度表示法。

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

數(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)系。

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

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

算法的執(zhí)行時(shí)間與每行代碼的執(zhí)行次數(shù)成正比，用 T(n) = O(f(n)) 表示，其中 T(n) 表示算法執(zhí)行總時(shí)間，f(n) 表示每行代碼執(zhí)行總次數(shù)，而 n 往往表示數(shù)據(jù)的規(guī)模。這就是大 O 時(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 = n² 次，而且這里的循環(huán)是 ++i，和例子 2 的是 i++，是不同的，是先加與后加的區(qū)別。

那么這個(gè)方法需要執(zhí)行 ( n² + n² + n + n + 1 + 1 +1 ) = 2n² +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(n²)。

只關(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ī)模無關(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(n²)。

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

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

所以，總的時(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(nn) = O(n²) 。

多個(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)) 。

多項(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(n²) （平方階）、O(n³)（立方階）。

除了 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é)里面是這樣子的：

2⁰ 2¹ 2² ... 2^k ... 2^x = n

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

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

因?yàn)閷?duì)數(shù)之間是可以互相轉(zhuǎn)換的，log3n = log₃2 log₂n，所以 O(log₃n) = O(C log₂n)，其中 C=log₃2 是一個(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(lognn) = O(nlogn) 。

非多項(xiàng)式階：隨著數(shù)據(jù)規(guī)模的增長(zhǎng)，算法的執(zhí)行時(shí)間和空間占用暴增，這類算法性能極差。

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

O(2ⁿ)（指數(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ù)列，通過歸納證明法可以證明，當(dāng) n >= 1 時(shí) T(n) < (5/3)ⁿ，同時(shí)當(dāng) n > 4 時(shí) T(n) >= (3/2)ⁿ。
所以該方法的時(shí)間復(fù)雜度可以表示為 O((5/3)ⁿ)，簡(jiǎn)化后為 O(2ⁿ)。
可見這個(gè)方法所需的運(yùn)行時(shí)間是以指數(shù)的速度增長(zhǎng)的。
如果大家感興趣，可以試下分別用 1，10，100 的輸入大小來測(cè)試下算法的運(yùn)行時(shí)間，相信大家會(huì)感受到時(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ù)雜度上。基本上均攤結(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)景非常特殊，非常有限，這里不說)。

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

O(1) < O(logn) < (n) < O(nlogn) < O(n²) < O(n³) < O(2ⁿ) < O(n!) < O(nⁿ)

常見的時(shí)間復(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) 為語句關(guān)于 n 所占存儲(chǔ)空間的函數(shù)。

function print(n) {
 const newArr = []; // 第 2 行
 newArr.length = n; // 第 3 行
  for (let i = 0; i = 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(n²)，像 O(logn)、O(nlogn) 這樣的對(duì)數(shù)階復(fù)雜度平時(shí)都用不到。

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

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

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

筆者文章常更地址：

1. 微信公眾號(hào)
2. github
3. 全棧修煉

參考文章：

復(fù)雜度分析（上）：如何分析、統(tǒng)計(jì)算法的執(zhí)行效率和資源消耗？
(數(shù)據(jù)結(jié)構(gòu))十分鐘搞定算法時(shí)間復(fù)雜度