快還是慢？認識 Big-O（用快遞講）
不要被符號嚇到。Big-O 只是在問一件事：「資料變多 100 倍，要花多久？」
想像你是快遞員
你今天要送 n 個包裹。考試會問你：「這 n 個包裹要花多久送完？」
但答案不能寫「30 分鐘」——因為今天 5 個包裹、明天 500 個。 所以我們用「n 變多時，時間會怎麼變」來描述。
這就是 Big-O 在做的事。
Big-O 不在乎你跑得多快，只在乎當 n 變大時，時間會怎麼成長。
五個你必須認識的家族
來看五種「送 n 個包裹」的方式：
O(1) — 常數時間
你站在門口，幫客人按一下電梯。不管有幾個客人，按一次就好。
例子：陣列直接拿第 5 格 (A[5])。
O(log n) — 對數時間（超快）
你有一本厚電話簿要找「陳大明」。你不會從第一頁翻——你直接翻中間，看是不是陳，不是就翻一半的一半。 每一次都把問題砍一半。
例子：在排好的陣列中二分搜尋。1024 筆資料，最多找 10 次。
O(n) — 線性時間
你要把 n 個包裹一個一個從車上搬下來。多 1 個，多 1 趟。
例子：把陣列所有元素相加、找最大值、線性搜尋。
O(n²) — 平方時間（小心！）
你要把 n 個包裹兩兩配對（看哪兩個要合送）。 第 1 個要跟剩下 (n-1) 個比一輪、第 2 個跟 (n-2) 個比……加起來大概 n²/2 次。
例子：氣泡排序、選擇排序、巢狀 for 迴圈。
n = 1000 時，O(n) 跑 1000 次、O(n²) 跑 100 萬次——差 1000 倍。 n = 100 萬時，O(n²) 跑 1 兆次——直接卡死。 看到雙層 for 迴圈第一個反應：這是 O(n²)，能不能改進？
O(2ⁿ) — 指數時間（炸裂）
你發傳單給朋友 → 每個朋友再發給 2 個朋友 → 那 2 個再各發 2 個…… n 輪後有 2ⁿ 個人收到傳單。
n=20 → 100 萬，n=30 → 10 億，n=50 → 比宇宙原子還多。
例子：暴力解的「列出所有子集合」、沒做記憶化的費氏數列遞迴。
排排看：誰快誰慢
從快到慢：
直覺一點看實際數字 (n = 1000)：
| 複雜度 | 大約跑幾次 | 感覺 |
|---|---|---|
| O(1) | 1 | 一瞬間 |
| O(log n) | 10 | 一瞬間 |
| O(n) | 1,000 | 還好 |
| O(n log n) | 10,000 | 還好 |
| O(n²) | 1,000,000 | 開始慢 |
| O(2ⁿ) | 天文數字 | 跑不完 |
怎麼算 Big-O？三個口訣
考試常問「請分析這段 code 的時間複雜度」。記住這三招：
口訣 1：只看「最大那一項」
如果你算出來是 3n² + 5n + 100，只看 n²，答案是 O(n²)。
常數和小項在 n 變大時都不重要。
口訣 2：常數倍率直接丟掉
5n 是 O(n)，不是 O(5n)。常數倍率不寫。
口訣 3：看迴圈的「層數」和「條件」
迴圈每次把 i 加 1 → O(n)
迴圈每次把 i 乘 2 → O(log n)
看到 i *= 2、「砍一半」、「二分」——基本上就是 log n。
還有一個：空間複雜度
時間複雜度問「要花多久」，空間複雜度問「要用多少記憶體」。 算法一樣——看你開了多大的陣列、遞迴堆疊多深。
例：你開一個 size n 的陣列來存中繼結果 → 空間 O(n)。 你只用幾個變數 → 空間 O(1)。
題型一：給程式碼，問 Big-O。
sum = 0
for i = 1 to n:
for j = i to n:
sum = sum + 1怎麼想：外層 n 次，內層次數會遞減 (n, n-1, n-2, …)。總和大約 n(n+1)/2 → O(n²)。
題型二：兩個演算法比較哪個快。
直接看誰的最高次方項小。O(n log n) 比 O(n²) 快。
題型三：n = 1000 時跑幾次？ 直接代入。O(n²) 就是 1,000,000；O(n log n) 大約 10,000（log₂ 1000 ≈ 10）。
陷阱：看到 3n² 別寫成 O(3n²)——常數要丟掉。
這章記住三件事
- Big-O = n 變大時時間怎麼成長，不是實際秒數。
- 順序：
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)。 - 看迴圈的層數和加法/乘法，就能猜出 Big-O。
下一章開始進入排序——你會看到 O(n²) 和 O(n log n) 的差別有多誇張。
學習進度只存在你的瀏覽器，不會上傳。