Big O 符號：A-Level 計算機科學實際上期望什麼

Big O 符號出現在每份主要的 A-Level 計算機科學規範中（AQA、OCR、Edexcel），許多學生在這裡栽跟頭不是因為數學困難，而是因為他們從未看過它與實際程式碼的連結。這是一份實務說明，告訴你需要了解什麼，以及如何在考試中回答相關問題而不兜圈子。

Big O 實際測量的是什麼

Big O 描述的是演算法的執行時間（或記憶體使用量）如何隨著輸入大小（通常稱為 n）增加而成長。這不是以秒為單位的碼錶測量。這是一種描述成長速率的方式，讓你能夠獨立於硬體來比較演算法。

當你寫下 O(n) 時，你在說：如果我將輸入加倍，工作量大約也會加倍。O(n²) 代表輸入加倍時工作量大約會增加四倍。這種關係就是審題者想要你識別的，而不是精確的操作計數。

你必須掌握的複雜度

A-Level 考試中，這些複雜度一再出現：

• O(1) – 常數時間。透過索引存取陣列元素：arr[5]。不管陣列有多大。
• O(log n) – 對數。在已排序列表上進行二元搜尋。每一步都將搜尋空間減半。
• O(n) – 線性。單一迴圈遍歷列表，就像線性搜尋逐一檢查每個項目。
• O(n log n) – 線性對數。Merge sort 和 quicksort（平均情況）都在這個範圍內。
• O(n²) – 二次方。嵌套迴圈遍歷相同資料，這正是 bubble sort、insertion sort 和 selection sort 所做的。
• O(2ⁿ) – 指數。沒有記憶化的樸素遞迴 Fibonacci。會迅速變得不可行。

你應該能夠看著虛擬碼，一眼就判斷出它屬於這些中的哪一個，因為這基本上就是考試測試的內容。

讀懂程式碼的複雜度

每次都有效的方法：數出迴圈，看它們如何與 n 相關。

# O(n) - 一個迴圈，單次遍歷
for i in range(n):
    print(i)

# O(n^2) - 嵌套迴圈，都與 n 相關
for i in range(n):
    for j in range(n):
        print(i, j)

# O(log n) - 搜尋空間在每次迭代時減半
low, high = 0, n - 1
while low <= high:
    mid = (low + high) // 2
    if target == arr[mid]:
        break
    elif target < arr[mid]:
        high = mid - 1
    else:
        low = mid + 1

嵌套迴圈其中內層迴圈的範圍取決於 n 仍然是 O(n²)，即使看起來稍有不同（像是 for j in range(i) 而不是 for j in range(n) — 整體來說仍然是二次方，只是常數因子不同）。

小心那些完全不取決於 n 的迴圈。一個無論輸入大小多少都總是執行 10 次的迴圈是 O(1)，即使有迴圈存在。審題者喜歡在這裡隱藏題目。

常見排序演算法及其 Big O

這是常見的考試主題，因為它同時結合了兩個規範：排序演算法和複雜度。

演算法	最佳情況	最差情況
Bubble sort	O(n)	O(n²)
Insertion sort	O(n)	O(n²)
Merge sort	O(n log n)	O(n log n)
Binary search	O(1)	O(log n)
Linear search	O(1)	O(n)

Merge sort 的一致性（最佳和最差情況複雜度相同）如果問題問你為什麼會在大型資料集上選擇它而不選 bubble sort，值得明確提到。Bubble sort 的 O(n) 最佳情況只在有提前退出最佳化時適用，當一次遍歷中沒有發生交換時 — 如果你提到這個，要說出這個細節，因為有些審題機構預期這個。

學生遺失分數的地方

最大的問題：寫