Learning Objectives
- 說明演算法是什麼，並舉出它的五個特性：輸入、輸出、有限、明確、可行
- 分辨演算法要回答的兩個問題：答案對不對（正確性）、做得快不快（效率）
- 用反例找出演算法的錯誤，知道「試了幾個例子都對」不代表正確
- 用「數步驟」比較同一個問題的不同做法，而不是用碼表計時
一份寫得夠清楚的做法
老師請你在一疊考卷裡找出最高分。你大概會這樣做：拿起第一張，記住分數；接著一張一張看，遇到更高的就改記那個分數；全部看完，記住的就是最高分。
這段描述有幾個特點：從什麼開始（一疊考卷）、最後得到什麼（最高分）、每一步要做什麼都講清楚了，而且考卷看完就會停。 這樣一份「一步一步、照著做就能解決問題」的做法，就叫做演算法（algorithm）。
演算法不一定要用程式寫。食譜、組裝家具的說明書、銀行的開戶流程，都是寫給人照著做的步驟；寫成程式，只是讓電腦來照著做。 「演算法」這個詞來自九世紀的數學家花拉子米（al-Khwārizmī）：他的名字在中世紀的拉丁文譯本裡寫成 Algoritmi，後來演變成這個詞。
演算法軌要學的，就是各種常見問題（搜尋、排序、找最短路徑…）的好做法，以及怎麼判斷一個做法好不好。
每個範例都有 Python、C++、Java 三種寫法，可以用動畫上方的按鈕切換；選擇會記在瀏覽器裡，整頁一起換。三種寫法的輸出完全相同，差別只在語法。
演算法的五個特性
Donald Knuth 在《電腦程式設計藝術》（The Art of Computer Programming）第一卷，列出演算法的五個特性。用「找最高分」對照：
| 特性 | 意思 | 找最高分 |
|---|---|---|
| 輸入（input） | 開始前給定的資料，可以是零個或多個 | 一疊考卷的分數 |
| 輸出（output） | 至少產生一個結果，而且和輸入有關 | 最高分 |
| 有限（finiteness） | 一定會在有限的步驟內結束 | 考卷有幾張就看幾次，看完就停 |
| 明確（definiteness） | 每一步都只有一種解讀，不會模稜兩可 | 「比目前記住的分數高，就改記它」 |
| 可行（effectiveness） | 每一步都簡單到能實際做到 | 比較兩個數字的大小 |
反過來看，下面這些就不算演算法：
- 「加入適量的鹽」：多少才叫適量？不明確
- 「從 1 開始往上數，數到最大的整數為止」：整數沒有最大的，永遠停不下來，不有限
- 「選出明天會漲的股票」：沒有一個實際做得到的步驟，不可行
程式語言幫了很大的忙：if a[i] > best 只有一種意思，電腦不會「大概猜一下」。所以寫成程式之後，「明確」通常自動成立；要特別小心的是「有限」，也就是迴圈會不會停。
找最大值，順便數比較了幾次
這就是「找最高分」寫成程式。best 記住目前看過的最大值，comparisons 記錄做了幾次比較。best 只在看到 41、58 時改變；7 個元素總共比較了 6 次。
第一個問題：答案對不對
一個演算法要回答兩個問題。第一個是正確性（correctness）：對每一個合法的輸入，都要給出正確的答案。
「我試了三個例子都對」不代表正確。只要找到一個輸入讓它算錯，就足以證明演算法有錯；這個輸入叫做反例（counterexample）。
下面的 max_wrong 是很常見的寫法：把 best 先設成 0。成績都是正數時它算得對，所以很難察覺；
一旦資料全是負數（例如寒流時的氣溫、帳戶的損益），它就回傳 0，而 0 根本不在資料裡。
找到反例：全是負數的時候
第一組 [12, 5, 30] 兩個版本都回答 30。第二組 [-8, -3, -15]：錯誤版的 best 從 0 開始，沒有任何元素比 0 大，所以一直停在 0。正確版從第一個元素 -8 開始，最後得到 -3。
反例常藏在邊界情況
反例最常出現在邊界情況（edge case），也就是資料「長得不太一樣」的時候。寫完一個演算法，可以拿這張清單問自己：
| 邊界情況 | 找最大值的例子 |
|---|---|
| 全部是負數、或有 0 | [-8, -3, -15]：上面的錯誤版就倒在這裡 |
| 只有一個元素 | [42]：迴圈一次都不執行，答案就是 42 |
| 所有元素都相同 | [7, 7, 7] |
| 最大值在第一個或最後一個 | [99, 1, 2]、[1, 2, 99] |
| 沒有元素 | []：a[0] 不存在，要先決定這時該回傳什麼（或回報錯誤） |
要證明演算法一定正確，需要更嚴謹的論證，例如說明「每一輪結束時，best 都是目前看過的元素裡最大的」，後面的課會用到這種想法。 這一課先記住：測試只能找出錯誤，不能保證沒有錯誤。
想一想：什麼是演算法
下面哪一個步驟不符合演算法「明確」的要求？
「x 從 1 開始，每次把 x 加 2，直到 x 等於 100 為止」這段步驟違反了哪一個特性？
一位同學用 best = 0 寫找最大值，測了 [3, 9, 4]、[10, 20]、[5] 都對，於是說「我的程式是正確的」。最好的回應是？
第二個問題：做得快不快
第二個問題是效率（efficiency）。兩個做法都正確時，我們想知道哪一個比較快。
直覺的做法是拿碼表計時，但同一支程式在不同電腦、不同語言、甚至同一台電腦的不同時刻，跑出來的秒數都不一樣。 所以分析演算法時，改成數步驟：數它做了幾次基本運算（一次比較、一次加法、一次指定）。步驟數只和演算法本身與輸入有關，和電腦快慢無關。
例如找最大值：n 個元素要比較 n - 1 次，上面 7 個元素比了 6 次；資料變成 1,000 個，就是 999 次。
再看一個例子：計算 1 + 2 + 3 + … + n。
- 做法一：用迴圈一個一個加，要做 n 次加法
- 做法二：用等差數列的公式 n × (n + 1) ÷ 2，不管 n 多大都只要 3 次運算
兩個做法的答案相同，但 n 是一百萬時，一個要做一百萬次加法，另一個還是 3 次。
1 加到 n：迴圈與公式
sum_loop(10) 的迴圈跑 10 輪，ops 從 0 數到 10。sum_formula 不管 n 是 10 還是 10,000，都只執行一行就算出答案。這裡只數加到 total 的那一次加法；迴圈變數 i 每輪也要加 1，算進去的話次數是兩倍，但仍然和 n 成正比。
猜數字的兩種策略
朋友心裡想一個 1～100 的整數，你每猜一次，他會說「太大」「太小」或「答對了」。有兩種策略：
- 從 1 開始猜：1、2、3…，一個一個試
- 每次猜中間：先猜 50；他說太小，答案就在 51～100，再猜這段的中間 75；依此類推
兩種都一定猜得到（都正確），差別在要猜幾次。下面的程式讓兩種策略去猜同一個答案 70，數一數各猜了幾次。
數一數要猜幾次
第一種策略一次只排除一個數字，要猜 70 次。第二種策略每猜一次，lo～hi 的範圍就剩一半左右，7 次就猜到了。動畫很長，可以把進度拖到後段，直接看「每次猜中間」那一段（出現 lo、hi 之後）。
最壞要猜幾次
猜幾次會隨答案改變，所以我們通常問：最壞要猜幾次？
| 答案的範圍 | 從 1 開始猜，最壞 | 每次猜中間，最壞 |
|---|---|---|
| 1～100 | 100 次 | 7 次 |
| 1～1,000 | 1,000 次 | 10 次 |
| 1～1,000,000 | 1,000,000 次 | 20 次 |
範圍變大 1,000 倍，第一種策略的次數也變大 1,000 倍；第二種只從 10 次變成 20 次。 「每次猜中間」就是二分搜尋（binary search），第 04 課會詳細說明它為什麼這麼快、邊界要怎麼寫才不會錯。
演算法分析的核心想法就在這裡：比較的不是某一個 n 的步驟數，而是 n 變大時，步驟數怎麼跟著變大。下一課會把這個想法寫成 Big-O。
想一想：數步驟
用本課的方法找 1,000 個數字裡的最大值，總共要比較幾次？
這段程式會印出什麼？
count = 0
for i in range(0, 20, 3):
count += 1
print(count)
為什麼分析演算法時用「數步驟」，而不是直接看程式跑了幾秒？
實作：同時找最低分與最高分
請完成 min_max：走過一次陣列，同時找出最低分與最高分，並數總共比較了幾次（每個元素要和目前的最低分比一次、和目前的最高分比一次）。預期輸出在右邊；可以切換成你熟悉的語言。
重點整理
- 演算法是一步一步、照著做就能解決問題的做法；五個特性：輸入、輸出、有限、明確、可行
- 評價演算法要回答兩個問題：正確性（每個合法輸入都對）與效率（做得快不快）
- 一個反例就能證明演算法有錯；反例常藏在邊界情況：負數、只有一個元素、全部相同、空的資料
- 效率用數步驟衡量，不用碼表計時；找最大值要比較 n - 1 次
- 同一個問題可以有很不一樣的做法：1 加到 n 用迴圈要 n 次加法，用公式只要 3 次；猜 1～100 的數字，一個一個猜最壞 100 次，每次猜中間最壞 7 次
下一課：時間複雜度與 Big-O。我們會學怎麼數迴圈的步驟，並用 O(n)、O(n²)、O(log n) 描述「n 變大時，步驟數怎麼變大」。