JavaScript時(shí)間和空間復(fù)雜度實(shí)例分析

這篇文章主要講解了“JavaScript時(shí)間和空間復(fù)雜度實(shí)例分析”，文中的講解內(nèi)容簡(jiǎn)單清晰，易于學(xué)習(xí)與理解，下面請(qǐng)大家跟著小編的思路慢慢深入，一起來(lái)研究和學(xué)習(xí)“JavaScript時(shí)間和空間復(fù)雜度實(shí)例分析”吧！

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

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

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

分別用時(shí)間復(fù)雜度和空間復(fù)雜度兩個(gè)概念來(lái)描述性能問(wèn)題，二者統(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ù)雜度分析，將能編寫(xiě)出性能更優(yōu)的代碼，有利于降低系統(tǒng)開(kāi)發(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)。

2 . 加法法則：總復(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ù)雜度。

3 . 乘法法則：嵌套代碼的復(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) 。

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

5 . 多個(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è)例子中看到。

下面舉例說(shuō)明 O(logn)（對(duì)數(shù)階）：

let i=1;

while (i <= n)  {

   i = i * 2;

}

代碼是從 1 開(kāi)始，每次循環(huán)就乘以 2，當(dāng)大于 n 時(shí)，循環(huán)結(jié)束。

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

20 21 22 &hellip; 2k &hellip; 2x = n

所以，我們只要知道 x 值是多少，就知道這行代碼執(zhí)行的次數(shù)了，通過(guò) 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)。

下面舉例說(shuō)明 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) 。

2 . 非多項(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ù)列，通過(guò)歸納證明法可以證明，當(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)。

可見(jiàn)這個(gè)方法所需的運(yùn)行時(shí)間是以指數(shù)的速度增長(zhǎng)的。

如果大家感興趣，可以試下分別用 1，10，100 的輸入大小來(lái)測(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ù)雜度。

舉例說(shuō)明：

// 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)，并返回索引值，如果沒(méi)找到就返回 -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&mdash;&mdash;n-1 位置中和不在數(shù)組中。我們把每種情況下，查找需要遍歷的元素個(gè)數(shù)累加起來(lái)，然后再除以 n+1，就可以得到需要遍歷的元素個(gè)數(shù)的平均值，即：

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

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

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

這個(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)景非常特殊，非常有限，這里不說(shuō))。

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)

常見(jiàn)的時(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ù)雜度通過(guò)計(jì)算算法所需的存儲(chǔ)空間實(shí)現(xiàn)，算法的空間復(fù)雜度的計(jì)算公式記作：S(n) = O(f(n))，其中，n 為問(wè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 ，除此之外，剩下的代碼都沒(méi)有占用更多的空間，所以整段代碼的空間復(fù)雜度就是 O(n)。

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

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

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

平時(shí)我們?cè)趯?xiě)代碼時(shí)，是用 空間換時(shí)間 還是 時(shí)間換空間，可以根據(jù)算法的時(shí)間復(fù)雜度和空間復(fù)雜度來(lái)衡量。

感謝各位的閱讀，以上就是“JavaScript時(shí)間和空間復(fù)雜度實(shí)例分析”的內(nèi)容了，經(jīng)過(guò)本文的學(xué)習(xí)后，相信大家對(duì)JavaScript時(shí)間和空間復(fù)雜度實(shí)例分析這一問(wèn)題有了更深刻的體會(huì)，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是億速云，小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章，歡迎關(guān)注！