JS學習筆記#9 | Function的時間複雜度

Gilly null on Unsplash

時間複雜度（Time Complexity）

時間複雜度是指一個演算法在執行時所需要的時間，通常是根據輸入數據的大小𝑛來評估。時間複雜度的高低直接影響演算法在面對大量數據時的效率，因此理解時間複雜度有助於評估不同解法的性能。

Big O 表示法

Big O 表示法是用來描述演算法在輸入量無限增長時的運行時間趨勢。它幫助我們了解演算法的效率，並比較不同演算法在面對大量數據時的表現。

• 不包含低階項：Big O 表示法只保留運行時間的「主導項」（dominant term），也就是對增長趨勢影響最大的一項。例如: n² + n 的複雜度在 Big O 中表達為 O(n²)。
• 不包含首項系數：Big O 表示法忽略主導項前的常數系數，因為系數不改變增長的速度。例如: 5n² 和 3n² 的 Big O 表示都記為 O(n²)。

O(1) - 常數時間複雜度

這類演算法的執行時間不會隨著輸入的大小變化。

// 取出數組中的第一個元素
function getFirstElement(arr) {
  return arr[0];  // 執行固定動作，不管 arr 的長度
}

即便 n 增加，執行時間仍然不變。

O(n) - 線性時間複雜度

這類演算法的執行時間隨著輸入的大小而成比例地增加。

function sumArray(arr) {
  let sum = 0;
  for (let i = 0; i < arr.length; i++) {
    sum += arr[i];
  }
  return sum;
}

當 n 增加，執行時間成比例增加。

O(n²) - 平方時間複雜度

這類演算法的執行時間隨著輸入量平方增長。

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

當 n 增加，執行時間呈 n² 增長，即平方增長。

O(2ⁿ) - 指數時間複雜度

這種複雜度的演算法執行時間隨著輸入量指數增加，比如斐波那契數列的遞迴解法：

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

指數時間的增長非常快。當 n 增加，執行時間呈 2ⁿ 增長，導致非常高的運算量。

總結

Big O 表示法提供了一個方法來分析演算法隨著輸入增長的時間增長趨勢，能幫助我們判斷不同演算法隨著輸入量增長的效率，對優化程式效能至關重要。