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

成都創(chuàng)新互聯(lián)長期為上千多家客戶提供的網(wǎng)站建設(shè)服務(wù)，團(tuán)隊(duì)從業(yè)經(jīng)驗(yàn)10年，關(guān)注不同地域、不同群體，并針對不同對象提供差異化的產(chǎn)品和服務(wù)；打造開放共贏平臺，與合作伙伴共同營造健康的互聯(lián)網(wǎng)生態(tài)環(huán)境。為懷安企業(yè)提供專業(yè)的網(wǎng)站設(shè)計制作、成都網(wǎng)站建設(shè)，懷安網(wǎng)站改版等技術(shù)服務(wù)。擁有十載豐富建站經(jīng)驗(yàn)和眾多成功案例,為您定制開發(fā)。

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

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

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

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

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

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

和性能測試相比，復(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í)行時間與每行代碼的執(zhí)行次數(shù)成正比，用 T(n) = O(f(n)) 表示，其中 T(n) 表示算法執(zhí)行總時間，f(n) 表示每行代碼執(zhí)行總次數(shù)，而 n 往往表示數(shù)據(jù)的規(guī)模。這就是大 O 時間復(fù)雜度表示法。

3.2 時間復(fù)雜度

1）定義

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

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

例子1：

function aFun() {

    console.log("Hello, World!");      //  需要執(zhí)行 1 次

    return 0;       // 需要執(zhí)行 1 次

}

那么這個方法需要執(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 次

}

那么這個方法需要執(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ū)別。

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

2）特點(diǎn)

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

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

3.3 時間復(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 次，所以時間復(fù)雜度為 O(n)。

2 . 加法法則：總復(fù)雜度等于量級最大的那段代碼的復(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)，是個常量的執(zhí)行時間，不能反映增長變化趨勢，所以時間復(fù)雜度為 O(1)。

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

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

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

所以，總的時間復(fù)雜度就等于量級最大的那段代碼的時間復(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)。

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

4 . 多個規(guī)模求加法：比如方法有兩個參數(shù)控制兩個循環(huán)的次數(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，所以時間復(fù)雜度為 O(m+n)。

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

5 . 多個規(guī)模求乘法：比如方法有兩個參數(shù)控制兩個循環(huán)的次數(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，所以時間復(fù)雜度為 O(m*n)。

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

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

多項(xiàng)式階：隨著數(shù)據(jù)規(guī)模的增長，算法的執(zhí)行時間和空間占用，按照多項(xiàng)式的比例增長。

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

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

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

let i=1;

while (i <= n)  {

   i = i * 2;

}

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

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

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

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

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

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

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

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

下面舉例說明 O(nlogn)（對數(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 的時間復(fù)雜度為 O(logn)，而 cal 的時間復(fù)雜度為 O(n)，所以上面代碼的時間復(fù)雜度為 T(n) = T1(logn) * T2(n) = O(logn*n) = O(nlogn) 。

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

包括 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，同時 T(n) = T(n - 1) + T(n - 2) + 1，這里的 1 是其中的加法算一次執(zhí)行。

顯然 T(n) = T(n - 1) + T(n - 2) 是一個斐波那契數(shù)列，通過歸納證明法可以證明，當(dāng) n >= 1 時 T(n) < (5/3)n，同時當(dāng) n > 4 時 T(n) >= (3/2)n。

所以該方法的時間復(fù)雜度可以表示為 O((5/3)n)，簡化后為 O(2n)。

可見這個方法所需的運(yùn)行時間是以指數(shù)的速度增長的。

如果大家感興趣，可以試下分別用 1，10，100 的輸入大小來測試下算法的運(yùn)行時間，相信大家會感受到時間復(fù)雜度的無窮魅力。

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

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

最好情況時間復(fù)雜度（best case time complexity）：在最理想的情況下，執(zhí)行這段代碼的時間復(fù)雜度。

最壞情況時間復(fù)雜度（worst case time complexity）：在最糟糕的情況下，執(zhí)行這段代碼的時間復(fù)雜度。

平均情況時間復(fù)雜度（average case time complexity），用代碼在所有情況下執(zhí)行的次數(shù)的加權(quán)平均值表示。也叫 加權(quán)平均時間復(fù)雜度 或者 期望時間復(fù)雜度。

均攤時間復(fù)雜度（amortized time complexity）: 在代碼執(zhí)行的所有復(fù)雜度情況中絕大部分是低級別的復(fù)雜度，個別情況是高級別復(fù)雜度且發(fā)生具有時序關(guān)系時，可以將個別高級別復(fù)雜度均攤到低級別復(fù)雜度上。基本上均攤結(jié)果就等于低級別復(fù)雜度。

舉例說明：

// n 表示數(shù)組 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 函數(shù)實(shí)現(xiàn)的功能是在一個數(shù)組中找到值等于 x 的項(xiàng)，并返回索引值，如果沒找到就返回 -1 。

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

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

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

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

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

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

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

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

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

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

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

均攤時間復(fù)雜度

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

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

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

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

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

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

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

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

定義：算法的空間復(fù)雜度通過計算算法所需的存儲空間實(shí)現(xiàn)，算法的空間復(fù)雜度的計算公式記作：S(n) = O(f(n))，其中，n 為問題的規(guī)模，f(n) 為語句關(guān)于 n 所占存儲空間的函數(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])

  }

}

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

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

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

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

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

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

網(wǎng)站標(biāo)題：JavaScript時間和空間復(fù)雜度實(shí)例分析
網(wǎng)站鏈接：http://www.chinadenli.net/article20/gepdco.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)頁設(shè)計公司、用戶體驗(yàn)、企業(yè)建站、Google、網(wǎng)站制作、品牌網(wǎng)站制作

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)