Foundations · 01 / 03

Big-O Notation時間與空間複雜度

用輸入大小 n 描述成本的成長速度。

用在：估算程式能不能撐住資料量、面試必問

時間複雜度—

空間複雜度—

難度入門

前置知識無，這是起點

01為什麼需要它

測試機很快，上線就超時

本機測 100 筆資料 0.01 秒，上線後 100 萬筆資料卻跑不完。兩層迴圈的程式，資料多一萬倍，時間多一億倍。

為什麼用它Big-O 描述「時間怎麼隨資料量成長」，讓你在寫程式時就預測這件事，而不是上線後才發現。

面試官問「這樣的複雜度是多少」

幾乎每一題演算法面試都會追問時間與空間複雜度，並要求你改進。這是業界共同的語言。

為什麼用它說 O(n²) 比說「大概要跑很久」精確得多，而且每個人聽到都知道是什麼意思。

決定值不值得優化

同事說要把某個函式從 O(n) 改成 O(log n)，但那個函式的 n 永遠不超過 10。

為什麼用它Big-O 是成長趨勢，不是絕對速度。知道它的意義，也就知道什麼時候不用管它。

看到這些關鍵字就想到它：這段程式的複雜度、資料量變十倍會慢幾倍、能不能更快、n 是多少。

02核心概念

Big-O 回答一個問題：輸入大小 n 變大時，程式要做的事以多快的速度增加？它不是精確的秒數，而是成長的「形狀」。O(n) 表示成長是一條直線，O(n²) 是拋物線，O(log n) 幾乎是平的。

操作次數隨 n 的成長O(1)O(log n)O(n)O(n log n)O(n²)O(2ⁿ)

y 軸只畫到 60，標了 ↑ 的曲線在那之前就衝出去了：O(2ⁿ) 在 n = 6 就超過 60，O(n²) 在 n = 8。O(log n) 和 O(1) 幾乎貼在底部。滑過圖表可看每個 n 的數值。

因為只在意形狀，Big-O 有兩條簡化規則：丟掉常數（3n 和 n 都是 O(n)），只留最大的項（n² + n 是 O(n²)）。這兩條規則讓不同機器、不同語言寫出的同一個演算法，能用同一個記號比較。

空間複雜度用同樣的方式描述額外用掉的記憶體。常見的取捨是用空間換時間：多開一個雜湊表，把 O(n²) 的比對變成 O(n)。

常見的複雜度由快到慢：O(1) → O(log n) → O(n) → O(n log n) → O(n²) → O(2ⁿ) → O(n!)。前四個在百萬級資料都跑得動，後三個很快就不行了，下面的示範可以親手感受這件事。

03演算法步驟

1找出「n」是什麼：陣列長度、字串長度、節點數。有兩個輸入就用兩個變數，例如 O(m·n)。
2看迴圈的層數與範圍：一層跑 n 次是 O(n)，兩層巢狀各跑 n 次是 O(n²)，每次把範圍砍半的迴圈是 O(log n)。
3看呼叫的函式裡面做了什麼：迴圈裡呼叫一個 O(n) 的函式，整體就是 O(n²)。內建的 sort 是 O(n log n)，in 對 list 是 O(n)、對 set 是 O(1)。
4把各段相加，然後丟掉常數與較小的項：2n² + 5n + 100 → O(n²)。
5預設報最壞情況。若題目強調平均或攤銷，再另外說明。

04互動示範

切換 n 的大小，比較七種複雜度的操作次數。右邊那欄假設每次操作 1 奈秒，換算成實際要等多久。

輸入大小 n =

長條為對數刻度，否則後面幾列會塞不下

複雜度相對規模操作次數每次 1 ns 要花

O(1)常數

11 ns

O(log n)對數

44 ns

O(n)線性

2020 ns

O(n log n)線性對數

8686 ns

O(n²)平方

400400 ns

O(2ⁿ)指數

1.05×10^61.0 ms

O(n!)階乘

2.43×10^1877.1 年

n 很小時每種複雜度都很快，這就是為什麼小資料不用在意演算法。把 n 調大看看。

05程式碼

同一個「有沒有重複元素」的問題，兩種寫法差一個 n。看程式時練習用上面的步驟數出每一段的複雜度。

# O(1)：不管 n 多大，做的事一樣多
def first(items):
    return items[0]

# O(n)：迴圈跑 n 次
def total(items):
    s = 0
    for x in items:
        s += x
    return s

# O(n²)：兩層迴圈各跑 n 次
def has_duplicate_slow(items):
    n = len(items)
    for i in range(n):
        for j in range(i + 1, n):
            if items[i] == items[j]:
                return True
    return False

# O(n)：用雜湊集合換掉內層迴圈，空間從 O(1) 變成 O(n)
def has_duplicate(items):
    seen = set()
    for x in items:
        if x in seen:
            return True
        seen.add(x)
    return False

# O(log n)：每一步把範圍砍半
def binary_search(sorted_items, target):
    lo, hi = 0, len(sorted_items) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if sorted_items[mid] == target:
            return mid
        if sorted_items[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

06練習題

這幾題的重點不是解出來，而是先寫暴力解、算出複雜度，再想辦法降一階。

LeetCode 217Contains Duplicate（O(n²) → O(n)）Easy
LeetCode 1Two Sum（O(n²) → O(n)）Easy
LeetCode 704Binary Search（O(n) → O(log n)）Easy
LeetCode 189Rotate Array（O(n) 時間、O(1) 空間）Medium