Learning Objectives
- 數出單層迴圈、雙層迴圈、三角形雙層迴圈與「每次減半」迴圈的基本運算次數
- 用 Big-O 描述步驟數的成長：去掉常數與低次項，只留最高次項
- 比較 O(1)、O(log n)、O(n)、O(n log n)、O(n²)、O(2ⁿ) 在 n 變大時的差距
- 分辨同一個演算法的最好、最壞、平均情況
- 說明空間複雜度：演算法額外用了多少記憶體
資料變大時，程式會慢多少
你寫了一支程式檢查班上 40 個人裡有沒有兩個人學號重複，一下就跑完了。換成全校兩萬人，它會慢 500 倍？還是慢 25 萬倍？還是根本跑不完？
上一課說過，分析演算法不看秒數，而是數基本運算的次數。這一課要做兩件事：
- 看程式的結構（幾層迴圈、迴圈怎麼變化），數出步驟數和 n 的關係
- 用 Big-O 把這個關係寫成簡短的式子，例如 O(n)、O(n²)，一眼看出 n 變大時會慢多少
這裡的 n 是輸入的大小：陣列的長度、要排序的資料筆數、圖的節點數等等。
單層迴圈與雙層迴圈
single_loop(n) 的迴圈跑 n 輪，count 數到 n。double_loop(n) 外層每跑一輪，內層就完整跑 n 輪，所以是 n × n 次。n 從 4 變成 8（2 倍），單層從 4 次變成 8 次（2 倍），雙層從 16 次變成 64 次（4 倍）。
每一對只比一次：三角形的雙層迴圈
開頭的問題「有沒有兩個人學號重複」，最直接的做法是每兩個人比一次。
內層迴圈的 j 從 i + 1 開始，因為「第 2 個和第 5 個」比過了，就不必再比「第 5 個和第 2 個」，自己和自己也不用比。
這樣內層的輪數一輪比一輪少：i = 0 時比 n - 1 次，i = 1 時比 n - 2 次……最後一輪 0 次。加起來是
(n - 1) + (n - 2) + … + 1 + 0 = n(n - 1) / 2
把 i、j 的組合畫成表格，比過的格子剛好是對角線右上方的三角形，所以常叫三角形的雙層迴圈。
每兩個比一次，數比較次數
看 j 永遠在 i 的右邊。i = 0 時 j 走 5 格，i = 1 時走 4 格……6 個元素總共比 5 + 4 + 3 + 2 + 1 = 15 次，和公式 n(n - 1) / 2 相同。索引 1 和 3 的 7 是唯一相同的一對。
每次砍一半：log n
有些迴圈不是每輪加 1，而是每輪把問題砍掉一半，例如上一課「每次猜中間」的猜數字。這種迴圈跑的輪數，是「n 要除以 2 幾次才會剩 1」，也就是 log₂n。
| n | 對半幾次剩 1 |
|---|---|
| 8 | 3 |
| 1,000 | 9 |
| 1,000,000 | 19 |
n 變大一百萬倍，次數只多十幾次。log₂n 是演算法裡最常出現的「慢慢長」的函數。
數一數要對半幾次
看上方的 n 每一輪變成一半（整數除法，捨去小數）。1,000 只要 9 次就剩 1，1,000,000 也只要 19 次。
Big-O：只看最高次項
真實的程式不會只有一個迴圈。假設數出來某個演算法要做
3n² + 5n + 2 次基本運算
n 很大時，3n² 遠遠超過 5n + 2：n = 1,000 時，3n² 是 300 萬，5n + 2 只有 5,002。而前面的係數 3 是由「一次比較算一步還是兩步」這類細節決定的，換個語言或寫法就會變。
所以描述成長率時，我們去掉常數係數、去掉低次項，只留最高次項，寫成 O(n²)，讀作「Big-O of n 平方」或「n 平方等級」。
幾個例子：
| 數出來的步驟數 | Big-O |
|---|---|
| 2n + 10 | O(n) |
| n(n - 1) / 2 ＝ 0.5n² - 0.5n | O(n²) |
| 4 log₂n + 7 | O(log n) |
| 3n log₂n + 20n | O(n log n) |
| 12（和 n 無關） | O(1) |
嚴格的定義是：如果存在常數 c 和 n₀，使得 n ≥ n₀ 時步驟數都 ≤ c × g(n)，就說步驟數是 O(g(n))。白話說，O(g(n)) 是一個上界：n 夠大以後，步驟數不會比 g(n) 的某個倍數還多。 log 的底數也可以省略，因為 log₂n 和 log₁₀n 只差一個常數倍。
O 這個符號由數學家 Paul Bachmann 在 1894 年提出、Edmund Landau 推廣，原本用在數論；1976 年 Donald Knuth 在〈Big Omicron and Big Omega and Big Theta〉一文中提倡把它用在演算法分析，之後成為電腦科學的標準寫法。
常見的成長率，由慢到快：
| Big-O | 名稱 | 典型例子 |
|---|---|---|
| O(1) | 常數時間 | 用索引讀取陣列元素、1 加到 n 的公式 |
| O(log n) | 對數時間 | 二分搜尋（第 04 課） |
| O(n) | 線性時間 | 找最大值、線性搜尋 |
| O(n log n) | 線性對數時間 | 合併排序（第 07 課） |
| O(n²) | 平方時間 | 每兩個比一次、簡單排序（第 06 課） |
| O(2ⁿ) | 指數時間 | 列出所有子集合 |
下面的小工具把這幾條曲線畫在一起，用滑桿把 n 拉大，看它們怎麼分開。
從小工具看到的事
- n 很小的時候（例如 n = 5），n² 是 25、n log₂n 約 11.6，只差兩倍多，看不出什麼。Big-O 談的是 n 很大時的趨勢
- n² 和 n log₂n 的比值是 n ÷ log₂n，n 越大差越多；要到 n = 997，n² 才第一次超過 n log₂n 的 100 倍。資料有幾百萬筆時，O(n²) 和 O(n log n) 的排序可能就是「幾秒」和「幾天」的差別
- 2ⁿ 在 n = 50 時，每秒一億次也要算一百多天；n 只要再加 10，時間就變成 2¹⁰ = 1,024 倍，要好幾百年。指數時間的演算法只能處理很小的 n
- 線性刻度下，最大的那條曲線會把其他曲線壓得貼在地上；對數刻度把「乘以 10」畫成同樣的高度，才看得出每條曲線的相對位置
想一想：這段程式是哪一級
下面的程式，時間複雜度是多少？
for i in range(n):
for j in range(10):
total += a[i] * j
某個演算法要做 5n² + 300n + 1000 次運算，用 Big-O 表示是？
這段程式會印出什麼？
n = 5
count = 0
for i in range(n):
for j in range(i):
count += 1
print(count)
下面的迴圈，時間複雜度是多少？
i = 1
while i < n:
i = i * 2
最好、最壞、平均情況
同一個演算法、同樣大小的 n，步驟數還可能隨資料的內容而不同。例如「找第一個不及格的成績」：
- 最好情況（best case）：第一個就不及格，比 1 次
- 最壞情況（worst case）：沒有人不及格，n 個全部比完
- 平均情況（average case）：在所有可能的輸入上取平均，需要假設資料怎麼分布
分析時通常看最壞情況，因為它是保證：再怎麼倒楣都不會超過這個次數。所以我們說這個演算法是 O(n)，雖然運氣好時只要 1 次。
同一個演算法，三種情況
三組成績都是 6 個。第一組第 0 個就是 45，比 1 次；第二組在索引 3 找到 52，比 4 次；第三組全部及格，6 個都要比。
空間複雜度：額外用了多少記憶體
除了時間，演算法也會用記憶體。空間複雜度（space complexity）描述的是演算法額外需要多少記憶體（輸入本身不算），一樣用 Big-O 表示。
def total(a): # 額外空間 O(1)：不管 a 多長，只多用了 s 和 x 兩個變數
s = 0
for x in a:
s += x
return s
def doubled(a): # 額外空間 O(n)：建立一個和 a 一樣長的新串列
result = []
for x in a:
result.append(x * 2)
return result
時間和空間常常可以互相交換：多用一些記憶體記住算過的結果，就能少算很多次（第 12 課的雜湊表、第 21 課的動態規劃都是這個想法）。 遞迴呼叫也會用到記憶體，每一層呼叫都要記住自己的變數，第 05 課會看到。
想一想：情況與空間
一個 O(n²) 的程式處理 1,000 筆資料要 2 秒。資料變成 3,000 筆，大約要多久？
關於「線性搜尋在最好情況只要比 1 次」，下面哪個說法正確？
把一個長度 n 的陣列「原地」反轉（只用兩個索引從兩端往中間交換），額外空間是多少？
實作：n 變 2 倍，次數變幾倍
請完成 count_pairs(n)：用三角形的雙層迴圈（j 從 i + 1 開始）數出「每兩個比一次」總共要比幾次。程式會印出 n = 4、8、16 的結果，並和公式 n(n - 1) / 2 對照。觀察 n 每變成 2 倍，次數大約變成幾倍。
重點整理
- 數基本運算的次數：單層迴圈 n 次、雙層迴圈 n² 次、每一對只比一次的三角形迴圈 n(n - 1) / 2 次、每次砍一半的迴圈 log₂n 次
- Big-O 去掉常數係數與低次項，只留最高次項：3n² + 5n + 2 是 O(n²)；它描述的是 n 很大時步驟數的上界
- 常見的成長率由慢到快：O(1)、O(log n)、O(n)、O(n log n)、O(n²)、O(2ⁿ)；n 很大時差距非常懸殊，2ⁿ 只能處理很小的 n
- 同一個演算法有最好、最壞、平均情況；通常看最壞情況，因為它是保證
- 空間複雜度看演算法額外用了多少記憶體，例如原地處理是 O(1)、建立同樣長的新陣列是 O(n)
下一課：陣列與串列的操作成本。用索引讀取為什麼是 O(1)？在最前面插入為什麼是 O(n)？Python 的串列一直 append，為什麼平均還是很快？