JavaScript時間復雜度和空間復雜度

前言

在上一篇文章中介紹瞭算法和數據結構的基本概念，這篇文章來介紹一下時間復雜度和空間復雜度。

時間復雜度和空間復雜度是衡量一個算法是否優秀的標準，通常我們比較兩個算法時會用到以下兩種方法：

預先估算：就是說在算法設計出來之後，根據算法中的步驟，去估算這個算法所需的時間復雜度和空間復雜度，然後兩個進行比較，選擇更優秀的那個；
事後統計：根據兩個算法分別編寫一個可執行程序/腳本，交給計算機去執行，分別記錄兩個算法所需要的時間復雜度和空間復雜度，然後兩個進行比較，選擇更優秀的那個。、

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

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

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

let i = 0
console.log(i)

因為在這個代碼中，這兩行代碼永遠隻執行一次，所以時間復雜度是`O(1)`

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

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

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)
}

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

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

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

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

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

現在我們來看一下幾個例子：

let i = 0
console.log(i)

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

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

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

O(n^2)

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

到此這篇關於JavaScript時間復雜度和空間復雜度的文章就介紹到這瞭,更多相關JavaScript時間復雜度內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！