Learning Objectives
- 說明什麼是演算法，以及一個好的演算法要具備的特性
- 用「數基本步驟」比較同一個問題的不同解法，而不是用秒數比較
- 用 Big-O 表示步數隨資料量 n 成長的速度：只看最高次項、去掉常數
- 分辨 O(1)、O(log n)、O(n)、O(n log n)、O(n²)、O(2ⁿ)，並各舉一個例子
- 說明最壞情況與空間複雜度的意思
同一個問題，可以有很多種解法
手機通訊錄只有 30 個人時，不管用什麼方法找人，一眨眼就找到了。可是如果是一所大學的 3 萬筆學生資料， 或是一個購物網站的上億筆訂單，「怎麼找」就會決定你要等 0.01 秒還是好幾分鐘。
演算法（algorithm）是解決一個問題的一連串明確步驟，就像食譜：照著做，一定會得到結果。 algorithm 這個字來自九世紀數學家花拉子米（al-Khwarizmi）名字的拉丁文寫法。一個演算法通常要符合這些條件：
| 特性 | 意思 |
|---|---|
| 輸入 | 有零個或多個資料當作起點 |
| 輸出 | 至少產生一個結果 |
| 明確 | 每一步都清楚，不會有兩種解讀 |
| 有限 | 一定會在有限的步驟內結束，不會永遠做下去 |
| 可行 | 每一步都是真的做得到的基本動作 |
這一課要回答的問題是：同一個問題有兩種解法，怎麼知道哪一種比較快？資料變多時，它會慢多少？
不比秒數，改數步驟
最直覺的比法是「各跑一次，看誰花的秒數少」。但秒數會受很多和演算法無關的因素影響：
- 電腦的 CPU 快慢、記憶體大小
- 用的程式語言、編譯器
- 電腦同時還在跑哪些程式
所以分析演算法時，改數基本步驟的次數：一次加法、一次比較、一次指派，都算一步。 更重要的不是「剛好幾步」，而是資料量 n 變大時，步數怎麼跟著長。
下面的範例用兩種方法算 1 + 2 + … + n。第一種一個一個加；第二種用國中學過的梯形公式（首項加末項，乘以項數，除以 2）。
兩種解法：一個一個加與公式
按 ▶ 自動播放，或用「下一步」一步一步看。注意上方的 steps：迴圈每跑一圈就多一次加法，一共跑了 n 圈。公式只有一行，不管 n 是 6 還是 6 億都只算一次。
資料量變大時差多少
把兩種解法的步數列出來：
| n | 一個一個加（約 n 步） | 公式（固定幾步） |
|---|---|---|
| 6 | 6 | 1 |
| 1,000 | 1,000 | 1 |
| 1,000,000 | 1,000,000 | 1 |
一個一個加的步數和 n 成正比：n 變成 10 倍，步數也變成 10 倍，這叫線性成長。 公式的步數不管 n 多大都一樣，這叫常數時間。
很多問題沒有這麼漂亮的公式，但常常有「步數長得比較慢」的解法。下一個範例是一個步數長得比較快的例子：兩兩配對。
雙層迴圈：每兩個人握一次手
外層的 i 每換一個人，內層的 j 就要和他後面的每一個人握手。看上方兩個 ▲ 怎麼移動，以及 count 最後是多少。最後三行直接用公式算 10、100、1000 人的握手次數。
Big-O：只看成長最快的部分
握手的次數是 n × (n - 1) ÷ 2 = 0.5n² - 0.5n。n 是 1,000 時，0.5n² 是 500,000，0.5n 只有 500，幾乎可以忽略。 人數變成 10 倍，次數大約變成 100 倍，這叫平方成長。
描述成長速度時，我們用 Big-O 記號，只保留重點，規則有兩條：
- 只留最高次項：n² + n + 10 寫成 O(n²)，因為 n 很大時，其他項相對很小
- 去掉常數倍數：0.5n²、3n² 都寫成 O(n²)，因為常數會隨電腦、語言改變，不影響「成長的形狀」
常見的等級，由慢到快長：
| Big-O | 名稱 | 例子 |
|---|---|---|
| O(1) | 常數 | 用公式算總和；陣列用索引讀一個元素 |
| O(log n) | 對數 | 猜數字每次猜中間；在排好的資料裡用二分搜尋 |
| O(n) | 線性 | 一個一個看，例如找最大值 |
| O(n log n) | 線性對數 | 好的排序方法（第 26 課） |
| O(n²) | 平方 | 兩兩配對、比較簡單的排序方法 |
| O(2ⁿ) | 指數 | 列出所有可能的組合，例如 n 個開關的所有開關狀態 |
O(log n) 的 log₂n 是「2 要乘幾次才會超過 n」，也就是「n 一直對半切，切幾次會剩 1 個」。下一個範例就來數這個次數。
對半再對半：猜數字要猜幾次
朋友心裡想一個 1 到 n 的數，你每次猜範圍的正中間，朋友回答「太大」或「太小」。最倒楣的情況下要猜幾次？看上方的 n 每一圈大約變成一半。size 從 1,000 變成 1,000,000（變成 1,000 倍），次數只從 10 變成 20。
從成長曲線看到的事
- n 從 100 變成 1,000，n² 從 10,000 變成 1,000,000，變成 100 倍。資料多 10 倍，O(n²) 的程式大約慢 100 倍
- n² 是 n 的 n 倍，所以 n 超過 100 之後，n² 就比 n 的 100 倍還多。n 很小的時候，各種等級差不多；Big-O 在意的是 n 很大時的趨勢
- 2ⁿ 在 n = 50 時，每秒一億次運算也要算一百多天；n 每多 1，時間就變成 2 倍。指數時間的方法只能處理很小的 n
- 線性刻度下，最大的那條曲線會把其他曲線壓得貼在地上；對數刻度把「乘以 10」畫成一樣的高度，才看得出順序：1、log₂n、n、n log₂n、n²、2ⁿ
想一想：數步驟與 Big-O
下面的程式，時間複雜度是多少？
for i in range(n):
for j in range(n):
print(i, j)
某個演算法要做 3n² + 2n + 7 個步驟，用 Big-O 表示是？
下面的程式會印出什麼？
count = 0
n = 8
while n > 1:
n = n // 2
count += 1
print(count)
最好、最壞與平均情況；還有記憶體
同一個演算法，步數也可能和資料長什麼樣子有關。例如在一份 n 個人的名單裡從頭一個一個找某個人：
| 情況 | 比較次數 |
|---|---|
| 最好：要找的人排第一個 | 1 |
| 最壞：排最後一個，或根本不在名單上 | n |
| 平均：每個位置的機會一樣 | 約 n ÷ 2 |
分析時最常看最壞情況，因為它保證「再慢也不會超過這樣」。上面的找人方法，最壞情況是 O(n)。
除了時間，演算法還會用到記憶體，這叫空間複雜度。例如算總和只需要 total 一個變數，是 O(1) 空間；
如果要先把 n 筆資料複製一份再處理，就需要 O(n) 的額外空間。有時候可以多用一點記憶體換取更快的速度，這是設計演算法常見的取捨。
想一想：資料變多時會怎樣
一個 O(n²) 的程式處理 1,000 筆資料要 2 秒。資料變成 2,000 筆，大約要多久？
演算法 A 是 O(n)，演算法 B 是 O(n²)。n = 10 的時候，B 有沒有可能比 A 快？
在一份 500 人的名單裡從頭一個一個找某個人，最壞情況要比較幾次？
實作：找最大值，順便數比較次數
find_max 從第一個數開始，一個一個和目前最大的 best 比較。請完成 TODO：每比一次就讓 comparisons 加 1，而且 x 比 best 大時就把 best 換成 x。完成後看看 100 個數要比幾次：這是 O(n) 還是 O(n²)？
重點整理
- 演算法是解決問題的一連串明確步驟：有輸入、有輸出、每一步明確可行、在有限步驟內結束
- 比較演算法不看秒數，而是數基本步驟，並看資料量 n 變大時步數怎麼成長
- Big-O 只留最高次項、去掉常數：3n² + 2n + 7 是 O(n²)
- 常見等級由慢到快長：O(1)、O(log n)、O(n)、O(n log n)、O(n²)、O(2ⁿ)；資料多 10 倍，O(n²) 大約慢 100 倍
- log₂n 是「對半切幾次會剩 1 個」：一百萬筆資料只要約 20 次
- 分析時最常看最壞情況；除了時間，還有記憶體用量（空間複雜度）
下一課：資料結構。同樣一批資料，排成陣列、串列、堆疊、佇列、樹或圖，各種操作的步數也會不一樣。 想更深入演算法的分析方法，可以接著上演算法軌（第 01、02 課）。