Time Complexity 時間複雜度 - paulip114/blog GitHub Wiki

怎麽知道我的演算法時間複雜度是多少

要知道你的演算法的時間複雜度，可以從以下幾個角度來分析：

🔍 1. 看你的演算法主要做了什麼

找出關鍵操作，例如：

  • 迴圈（for、while）
  • 遞迴（recursion）
  • 巢狀結構（nested loops）
  • 資料結構操作（例如 insert、lookup、sort）

🧮 2. 分析迴圈數量和次數

舉幾個簡單例子：

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

// O(n^2)
for (let i = 0; i < n; i++) {
  for (let j = 0; j < n; j++) {
    console.log(i, j);
  }
}

// O(log n)
while (n > 1) {
  n = n / 2;
}

🔁 3. 如果有遞迴，寫出遞迴公式，然後推展時間複雜度

範例（費波那契數列）：

function fib(n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

這會產生一個時間複雜度為 O(2^n) 的演算法，因為每次都分出兩個子問題。

🔧 4. 看使用了什麼資料結構

不同資料結構的操作時間不同，例如：

  • 陣列 O(1) 查詢、O(n) 插入（中間）
  • HashMap：O(1) 插入與查詢
  • 二元搜尋樹：O(log n) 插入與查詢（平衡的情況下）

📏 5. 實際手動推估運算次數

假設 n = 10，你可以數一下實際跑了幾次，推測規則。

Cheat Sheet

image image image

📚 補充工具