前言

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

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

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

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

時間復(fù)雜度

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

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

• O(1)

let i = 0
console.log(i)

因為在這個代碼中，這兩行代碼永遠(yuǎn)只執(zhí)行一次，所以時間復(fù)雜度是`O(1)`

• O(n)

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

在上面的代碼中，運行時間取決與`n`，所以時間復(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)
}

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

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

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

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

空間復(fù)雜度

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

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

• O(1)

let i = 0
console.log(i)

???????因為在這個代碼中，僅僅定義了一個臨時變量，所以空間復(fù)雜度是`O(1)`

• O(n)

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

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

O(n^2)

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

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

最新評論