前言

在上一篇文章中介紹了算法和數(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)行對比，因?yàn)榈诙N在不同環(huán)境、不同語言、不同計算機(jī)下的運(yùn)行結(jié)果是有差異的，而且第二種的工作量也要比第一種要大。

時間復(fù)雜度

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

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

• O(1)

let i = 0
console.log(i)

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

• O(n)

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

在上面的代碼中，運(yùn)行時間取決與`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ù)雜度差不多，表示的是算法在運(yùn)行過程中臨時占用存儲空間的大小的一個計量單位，

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

• O(1)

let i = 0
console.log(i)

???????因?yàn)樵谶@個代碼中，僅僅定義了一個臨時變量，所以空間復(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)文章希望大家以后多多支持腳本之家！

最新評論