Complexity and Big O Notation

Complexity 複雜度

複雜度是用來衡量演算法執行效率的指標，主要分為時間複雜度和空間複雜度。

時間複雜度（Time Complexity）

時間複雜度用於衡量演算法執行所需的時間成本，通常以運算次數來表示。

1. 定義

• 描述演算法執行時間與輸入資料量的關係
• 不是實際的執行時間，而是運算次數的增長趨勢

2. 計算重點

• 關注最耗時的操作
• 忽略常數項和低次項
• 著重於資料量增長時的變化

空間複雜度（Space Complexity）

空間複雜度用於衡量演算法執行所需的額外記憶體空間。

1. 定義

• 描述額外記憶體使用量與輸入資料量的關係
• 不包括輸入資料本身占用的空間

2. 計算重點

• 臨時變數的使用
• 遞迴呼叫的堆疊空間
• 資料結構的額外空間

複雜度分析的三種情況

1. 最佳情況（Best Case）

• 演算法執行時的最理想情況
• 例如：搜尋時第一個就是目標值

2. 平均情況（Average Case）

• 一般執行情況下的平均表現
• 最常用來評估演算法效能

3. 最差情況（Worst Case）

• 演算法執行時的最糟糕情況
• 通常用大 O 符號表示
• 用於評估演算法的效能下限

為什麼需要複雜度分析

1. 效能評估

• 預測程式執行效率
• 比較不同演算法的優劣

2. 系統規劃

• 評估系統承載能力
• 預測資源使用情況

3. 最佳化決策

• 選擇合適的演算法
• 在時間和空間之間取得平衡

Big O Notation 大 O 表示法

大 O 表示法是用來描述演算法在最差情況下的執行時間複雜度，它表示了演算法執行時間與輸入資料量之間的增長關係。

常見的時間複雜度

1. O(1) - 常數時間

// 無論輸入大小，執行時間都相同
function getFirstElement(arr) {
  return arr[0];
}

2. O(log n) - 對數時間

// 二分搜尋是典型的對數時間複雜度
function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1;
}

3. O(n) - 線性時間

// 需要遍歷整個陣列一次
function findMax(arr) {
  let max = arr[0];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] > max) max = arr[i];
  }
  return max;
}

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

// 大多數排序演算法的時間複雜度
function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  
  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
  
  return merge(left, right);
}

5. O(n²) - 平方時間

// 巢狀迴圈，常見於簡單排序演算法
function bubbleSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
  return arr;
}

6. O(2ⁿ) - 指數時間

// 遞迴計算斐波那契數列
function fibonacci(n) {
  if (n <= 1) return n;
  return fibonacci(n - 1) + fibonacci(n - 2);
}

複雜度比較

從最快到最慢的排序：

1. O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)

實際應用考量

1. 常數因子

• 大 O 表示法忽略常數
• 實際執行時間仍受常數影響
• 小資料量時，常數因子更重要

2. 空間與時間的取捨

• 有時可以用空間換取時間
• 需根據實際情況選擇適當的解決方案

3. 最佳實踐

• 先求正確，再求效率
• 考慮實際應用場景
• 注意程式碼的可維護性

效能優化建議

1. 避免不必要的巢狀迴圈
2. 善用適當的資料結構
3. 考慮使用快取機制
4. 注意記憶體使用效率