Yoru Karu Studio
Yoru Karu Studio

演算法基礎：時間複雜度完全指南

從零開始理解 Big O 記法與演算法效率分析

luk 收錄於 Algorithm-Basics
 約 1000 字 預計閱讀 5 分鐘 

什麼是時間複雜度？

時間複雜度（Time Complexity）是用來描述演算法執行時間如何隨著輸入規模增長的數學模型。簡單來說，它回答了一個問題：「當資料量變大時，程式會跑多久？」

為什麼需要時間複雜度？

想像你要從一本電話簿中找到某個人的電話號碼：

# 方法 1：從頭翻到尾（線性搜尋）
def linear_search(phone_book, name):
    for entry in phone_book:
        if entry.name == name:
            return entry.phone
    return None

# 方法 2：利用排序特性（二分搜尋）
def binary_search(phone_book, name):
    left, right = 0, len(phone_book) - 1
    while left <= right:
        mid = (left + right) // 2
        if phone_book[mid].name == name:
            return phone_book[mid].phone
        elif phone_book[mid].name < name:
            left = mid + 1
        else:
            right = mid - 1
    return None

當電話簿有 1000 個號碼時，差異可能不明顯。但如果有 100 萬個號碼呢？這就是為什麼我們需要時間複雜度分析。

Big O 記法

Big O 記法是描述時間複雜度的標準方式。它關注的是最壞情況下的增長趨勢。

基本規則

  1. 忽略常數：O(2n) = O(n)
  2. 忽略低階項：O(n² + n) = O(n²)
  3. 關注最壞情況：即使平均很快，我們仍考慮最慢的情況

常見的時間複雜度

O(1) - 常數時間

無論輸入多大，執行時間都一樣。

def get_first_element(arr):
    """取得陣列的第一個元素"""
    if len(arr) > 0:
        return arr[0]
    return None

def lookup_dict(dictionary, key):
    """字典查找"""
    return dictionary.get(key)

# 無論陣列或字典多大，執行時間都一樣

O(log n) - 對數時間

每次操作都能排除一半的可能性。

def binary_search(arr, target):
    """二分搜尋法"""
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1

# 範例：在 1,000,000 個元素中搜尋
# 最多只需要 log₂(1,000,000) ≈ 20 次比較

O(n) - 線性時間

執行時間與輸入成正比。

def find_max(arr):
    """找出陣列中的最大值"""
    if not arr:
        return None
    
    max_val = arr[0]
    for num in arr:  # 需要看過每個元素
        if num > max_val:
            max_val = num
    
    return max_val

def count_occurrences(arr, target):
    """計算某個值出現的次數"""
    count = 0
    for num in arr:  # O(n)
        if num == target:
            count += 1
    return count

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

常見於高效的排序演算法。

def merge_sort(arr):
    """合併排序"""
    if len(arr) <= 1:
        return arr
    
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])    # 遞迴分割
    right = merge_sort(arr[mid:])
    
    return merge(left, right)

def merge(left, right):
    """合併兩個已排序陣列"""
    result = []
    i = j = 0
    
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    
    result.extend(left[i:])
    result.extend(right[j:])
    return result

O(n²) - 平方時間

巢狀迴圈的典型複雜度。

def bubble_sort(arr):
    """泡沫排序"""
    n = len(arr)
    for i in range(n):
        for j in range(0, n - i - 1):  # 雙層迴圈
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

def find_duplicates_naive(arr):
    """找出所有重複的配對（天真方法）"""
    duplicates = []
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):  # O(n²)
            if arr[i] == arr[j]:
                duplicates.append((i, j))
    return duplicates

O(2ⁿ) - 指數時間

每增加一個輸入，執行時間加倍。

def fibonacci_recursive(n):
    """遞迴計算費波那契數（效率很差）"""
    if n <= 1:
        return n
    return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)

# 計算 fibonacci(40) 需要超過 10 億次函數呼叫！

如何分析時間複雜度

步驟 1：識別基本操作 

def example_function(arr):
    total = 0                    # O(1)
    for i in range(len(arr)):    # O(n)
        total += arr[i]          # O(1)
    return total                 # O(1)

# 總時間複雜度：O(1) + O(n) × O(1) + O(1) = O(n)

步驟 2：分析迴圈 

def nested_loops_example(n):
    count = 0
    
    # 單層迴圈：O(n)
    for i in range(n):
        count += 1
    
    # 巢狀迴圈：O(n²)
    for i in range(n):
        for j in range(n):
            count += 1
    
    # 相依迴圈：O(n²)
    for i in range(n):
        for j in range(i):  # j 的範圍依賴 i
            count += 1
    
    return count

步驟 3：考慮遞迴 

def recursive_example(n):
    if n <= 0:
        return 1
    
    # 單次遞迴：O(n)
    return recursive_example(n - 1)

def binary_recursive(n):
    if n <= 0:
        return 1
    
    # 二分遞迴：O(log n)
    return binary_recursive(n // 2)

def double_recursive(n):
    if n <= 0:
        return 1
    
    # 雙重遞迴：O(2ⁿ)
    return double_recursive(n - 1) + double_recursive(n - 1)

實戰範例：比較不同複雜度 

import time
import matplotlib.pyplot as plt

def measure_time(func, *args):
    """測量函數執行時間"""
    start = time.time()
    result = func(*args)
    end = time.time()
    return end - start, result

# O(1) - 常數時間
def constant_time(n):
    return n * 2

# O(n) - 線性時間
def linear_time(n):
    total = 0
    for i in range(n):
        total += i
    return total

# O(n²) - 平方時間
def quadratic_time(n):
    total = 0
    for i in range(n):
        for j in range(n):
            total += 1
    return total

# 測試不同輸入大小
sizes = [10, 100, 1000, 5000]
results = {
    'O(1)': [],
    'O(n)': [],
    'O(n²)': []
}

for size in sizes:
    results['O(1)'].append(measure_time(constant_time, size)[0])
    results['O(n)'].append(measure_time(linear_time, size)[0])
    results['O(n²)'].append(measure_time(quadratic_time, size)[0])

# 結果會顯示：
# O(1) 幾乎不變
# O(n) 線性增長
# O(n²) 急速增長

常見陷阱與誤區

陷阱 1：忽略隱藏的複雜度 

# 看起來是 O(n)，實際上可能是 O(n²)
def sneaky_complexity(strings):
    result = ""
    for s in strings:  # O(n)
        result += s    # 字串連接在 Python 中是 O(k)，k 是當前字串長度
    return result

# 更好的做法：使用 join，真正的 O(n)
def better_approach(strings):
    return "".join(strings)

陷阱 2：最好情況 vs 最壞情況 

def find_element(arr, target):
    """
    最好情況：O(1) - 第一個就找到
    最壞情況：O(n) - 在最後或不存在
    平均情況：O(n/2) = O(n)
    """
    for i, val in enumerate(arr):
        if val == target:
            return i
    return -1

陷阱 3：空間換時間 

# 時間 O(n²)，空間 O(1)
def has_duplicate_slow(arr):
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            if arr[i] == arr[j]:
                return True
    return False

# 時間 O(n)，空間 O(n)
def has_duplicate_fast(arr):
    seen = set()
    for num in arr:
        if num in seen:
            return True
        seen.add(num)
    return False

實用建議

1. 先寫對，再優化 

# 版本 1：簡單但慢
def get_intersection_v1(list1, list2):
    intersection = []
    for item in list1:
        if item in list2 and item not in intersection:
            intersection.append(item)
    return intersection

# 版本 2：優化後
def get_intersection_v2(list1, list2):
    return list(set(list1) & set(list2))

2. 了解資料結構的複雜度 

# Python 內建資料結構的時間複雜度
# list: 
#   - append: O(1)
#   - insert(0, x): O(n)
#   - pop(): O(1)
#   - pop(0): O(n)
#   - x in list: O(n)

# dict/set:
#   - x in dict: O(1)
#   - dict[key]: O(1)
#   - dict[key] = value: O(1)

# 選擇正確的資料結構很重要！

3. 預先計算 

# 沒有預先計算：每次查詢都是 O(n)
def is_prime_slow(n):
    if n < 2:
        return False
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True

# 預先計算：建表 O(n log log n)，查詢 O(1)
def sieve_of_eratosthenes(limit):
    is_prime = [True] * (limit + 1)
    is_prime[0] = is_prime[1] = False
    
    for i in range(2, int(limit ** 0.5) + 1):
        if is_prime[i]:
            for j in range(i * i, limit + 1, i):
                is_prime[j] = False
    
    return is_prime

# 使用預先計算的結果
prime_table = sieve_of_eratosthenes(1000000)
def is_prime_fast(n):
    if n <= 1000000:
        return prime_table[n]
    return is_prime_slow(n)  # 大數字仍用原方法

總結

理解時間複雜度是寫出高效程式的關鍵。記住這些要點：

  1. Big O 關注增長趨勢，不是精確的執行時間
  2. 從簡單開始，需要時再優化
  3. 權衡很重要：時間、空間、程式碼可讀性
  4. 了解你的工具：熟悉常用資料結構和演算法的複雜度
  5. 實際測試：理論分析後，用真實數據驗證

下一篇文章，我們將深入探討空間複雜度，了解程式的記憶體使用如何隨輸入增長。

延伸閱讀

更新於 2025-01-23 
CC BY-NC-SA 4.0
閱讀原始文檔
AlgorithmPythonComplexity-AnalysisData-Structures
返回 | 主頁
0%