時間複雜度 (Big O Notation)

簡介

  • 因為在不同環境（電腦設備）下，運行的時間長短不一，難以單純使用運行時間判斷演算法的效率
  • 可以使用 Big O 幫助開發者理解在最壞的情況下，演算法的運行時間會如何隨著輸入數據量的增加而增長

是什麼

  • 計算這個方法裡面總共用了多少步驟
  • 執行時間隨著數據規模增長的變化趨勢
  • 會考慮最壞的情況

範例

  1. 賦值到變數
  • 一個步驟
  • 時間複雜度：O(1)
const name = 'Tom'
  1. 跑一個 N 次的迴圈
  • N 個步驟
  • 時間複雜度：Ｏ(N)
  • 迴圈的執行次數直接與 n 成比例
for (let i = 0; i < n; i++) {  console.log(i)}

可省略的部分

  • 重視的是數字成長的速度
  • 只會紀錄最高次方的那一項，並忽略其所有的係數
  • 當時間複雜度是O(N^2) + O(N) 時，會標記為 O(N^2)
  • O(2N) 可省略成 O(N)

rules

  • Constant doesn't matter
f(n) = 2n => O(n)
  • Small Terms don't matter
f(n) = 13n^3 + 6n + 7 => O(n^3)
  • Logarithm Base doesn't matter
f(n) = 4log2n => O(logn)

常見演算法表示方式

O(1): 常數時間

  • 演算法的執行時間是固定的，不會因為輸入數據的增加而改變

O(n): 線性增長

  • 當資料變 2 倍，時間變 2 倍
  • 舉例： for 迴圈遍歷一個數組。

O(n log n) - 線性對數時間

  • 常見於需要排序或其他形式的分治法的演算法
  • 舉例：快速排序

O(n^2) - 平方時間

  • 演算法的執行時間與輸入數據的大小的平方成正比
  • 舉例：雙重 for 迴圈遍歷二維數組

O(2^n) - 指數時間

  • 演算法的執行時間以指數形式增長，這類演算法通常是非常低效的
  • 舉例： 斐波那契數列的遞歸實現

e5b8b8e8a68be69982e99693e8a487e99b9ce5baa6.jpeg

Objects And Arrays

  • JS 當中的 Object 都會被轉換成 hashtable
  • 在物件中
    • 新增一個屬性 => O(1)
    • 移除一個屬性 => O(1)
    • 找到一個屬性 => O(1)
    • 找到一個屬性相對應的值 => O(1)
  • 在陣列中
    • push() => O(1)
    • unshift() => O(n) （因為從最前面加入，陣列中後面的 index 都需要改變）
    • pop() => O(1)
    • shift() => O(n)
    • 搜尋 => O(n)
    • 取得陣列中的值 => O(1)

範例

  • for loop 運行了 n 次，時間複雜度是 O(n)
  • unshift 的時間複雜度是 O(n)
  • 整體來說的時間複雜度是 O(n^2)
let n = 10let arr = [1, 3, 5, 7, 9]for (let i = 0; i < n; i++) {  arr.unshift(10) // O(n)}

參考資料

# Alogorithm # BigO