前言

在上一篇文章中介紹了算法和數(shù)據(jù)結(jié)構(gòu)的基本概念，這篇文章來介紹一下時(shí)間復(fù)雜度和空間復(fù)雜度。

時(shí)間復(fù)雜度和空間復(fù)雜度是衡量一個(gè)算法是否優(yōu)秀的標(biāo)準(zhǔn)，通常我們比較兩個(gè)算法時(shí)會用到以下兩種方法：

• 預(yù)先估算：就是說在算法設(shè)計(jì)出來之后，根據(jù)算法中的步驟，去估算這個(gè)算法所需的時(shí)間復(fù)雜度和空間復(fù)雜度，然后兩個(gè)進(jìn)行比較，選擇更優(yōu)秀的那個(gè)；
• 事后統(tǒng)計(jì)：根據(jù)兩個(gè)算法分別編寫一個(gè)可執(zhí)行程序/腳本，交給計(jì)算機(jī)去執(zhí)行，分別記錄兩個(gè)算法所需要的時(shí)間復(fù)雜度和空間復(fù)雜度，然后兩個(gè)進(jìn)行比較，選擇更優(yōu)秀的那個(gè)。、

通常情況下我們都會采用第一種方式進(jìn)行對比，因?yàn)榈诙N在不同環(huán)境、不同語言、不同計(jì)算機(jī)下的運(yùn)行結(jié)果是有差異的，而且第二種的工作量也要比第一種要大。

時(shí)間復(fù)雜度

所謂的時(shí)間復(fù)雜度就是用于定性描述算法所運(yùn)行需要花費(fèi)的時(shí)間，所謂的定性就是大概進(jìn)行描述一下運(yùn)行時(shí)間的趨勢，不會去具體到運(yùn)行需要多少秒；時(shí)間復(fù)雜度通常用大O來表示，例如O(1)、O(n)、O(logn)等。

接下來我們通過具體的代碼來展示一下時(shí)間復(fù)雜度，這樣更方便去理解：

• O(1)

let i = 0
console.log(i)

因?yàn)樵谶@個(gè)代碼中，這兩行代碼永遠(yuǎn)只執(zhí)行一次，所以時(shí)間復(fù)雜度是`O(1)`

• O(n)

for (let i = 0; i < n; i++) {
  console.log(i)
}

在上面的代碼中，運(yùn)行時(shí)間取決與`n`，所以時(shí)間復(fù)雜度是`O(n)`。

• O(logn)

let i = 1
while (i < n) {
  console.log(i)
  i *= 2
}

如果是下面這種情況：

let i = 0
console.log(i)
for (let i = 0; i < n; i++) {
  console.log(n)
}

它的時(shí)間復(fù)雜度是O(1) + O(n)，它最終的時(shí)間復(fù)雜度是O(n)，兩個(gè)時(shí)間復(fù)雜度相加的話一般會忽略較小的那個(gè)。

如果是兩個(gè)時(shí)間復(fù)雜度相乘的話，例如下面這段代碼：

for (let i = 0; i < n; i++) {
  for (let j = 0; j < n; j++) {
    console.log(j)
  }
}

這段代碼的時(shí)間復(fù)雜度是O(n^2)，如果是相乘的話會將兩個(gè)時(shí)間復(fù)雜度進(jìn)行相乘。

空間復(fù)雜度

空間復(fù)雜度與時(shí)間復(fù)雜度差不多，表示的是算法在運(yùn)行過程中臨時(shí)占用存儲空間的大小的一個(gè)計(jì)量單位，

現(xiàn)在我們來看一下幾個(gè)例子：

• O(1)

let i = 0
console.log(i)

???????因?yàn)樵谶@個(gè)代碼中，僅僅定義了一個(gè)臨時(shí)變量，所以空間復(fù)雜度是`O(1)`

• O(n)

const arr = []
for (let i = 0; i < n; i++) {
  arr.push(i)
}

???????在上面的代碼中，我們聲明了一個(gè)數(shù)組，每循環(huán)一次都要往數(shù)組中存儲一個(gè)變量，所以時(shí)間復(fù)雜度是`O(n)`

O(n^2)

let i = 1
while (i < n) {
  console.log(i)
  i *= 2
}

到此這篇關(guān)于JavaScript時(shí)間復(fù)雜度和空間復(fù)雜度的文章就介紹到這了,更多相關(guān)JavaScript時(shí)間復(fù)雜度內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論