時間空間復雜度詳解

什么是復雜度

• 程序執行時需要的計算量和內存空間（和代碼是否簡介無關系）
• 復雜度是數量級， 不是具體的數字
• 一般針對一個具體的算法，而非一個完整的系統

復雜度有如下幾種

• O(1) 可數的數量級
• O(logn) 隨著計算量越大 時間越平緩
• O(n) 輸入兩怎加 復雜度也增加
• O(nlogn) 隨著輸入量增大，復雜度明顯增大 也就是 第二種乘以第三種
• O(n^2) 輸入量增大， 復雜度指數級增長

時間復雜度

下面是幾種復雜度的對應的代碼幫助理解

O(1)

function fn (obj={}, key) {
  return onj[key]
}

O(n)

function fn (list = []) {
  for (let i=0; i<list.length;i++) {
    console.log(list[i])
  }
}

O(n^2)

function fn (list = []) {
  for (let i=0; i<list.length;i++) {
    for (let j=0; j<list.length;j++) {
      console.log(list[j])
    }
  }
}

O(logn)

二分

O(nlogn)

一次循環 嵌套一個二分

空間復雜度

常用的是三個 沒有 log

O(1)

function fn (arr=[]) {
  let a = arr[1]
  let b = arr[2]
}

O(n)

function fn (arr=[]) {
  const arr2 = []
  for (let i=0; i<arr.length;i++) {
    arr2[i] = arr[i]
  }
}

2周刷完100道前端優質面試真題 更多視頻及資料領取請關注公眾號：奮斗的剛子
歡迎體驗我的小程序