Classification of algorithms

歡迎來到演算法分類的世界！

在本章中，我們將深入探討計算理論（Theory of Computation）的核心。你已經學會了如何編寫演算法，但你有沒有想過，電腦科學家是如何判斷一個演算法是否「更優」的呢？如果你有兩種不同的方法來整理一份名單，當名單上有數百萬個名字時，你如何知道哪一種方法會更快？

我們將學習如何使用大 O 符號（Big-O notation）來衡量演算法的「效率」，並會發現有些問題是如此困難，以至於即使是世界上最強大的電腦，也無法在合理的時間內解決它們。如果一開始覺得這些概念有點抽象，不用擔心——我們會循序漸進地為你拆解！

1. 比較演算法

當我們比較演算法時，並不是看它們在你的手提電腦上運行需要多少秒。為什麼？因為更快的處理器總是會讓演算法看起來「更好」。相反，我們關注的是複雜度（Complexity）。

時間與空間效率

衡量演算法主要有兩種方式：
• 時間複雜度（Time Complexity）：隨著輸入規模增加，執行所需的時間是多少？
• 空間複雜度（Space Complexity）：隨著輸入增長，演算法需要多少記憶體（RAM）？

關鍵問題：問題規模 \( (n) \)
最重要的因素是問題規模（problem size），我們通常稱之為 \( n \)。例如，如果你要在名單中搜尋一個名字，\( n \) 就是名單中名字的數量。當 \( n \) 變大時，我們想知道電腦需要增加多少工作量。

比喻：想像你在整理房間。如果 \( n \) 是地板上物品的數量，「線性」演算法意味著整理 10 件物品需要 10 分鐘，整理 20 件需要 20 分鐘。但如果整理 20 件物品突然需要 400 分鐘，那你所用的演算法就非常沒有效率了！

重點小結：我們比較演算法是基於它們的效能如何隨問題規模 \( (n) \) 而變化，而不是基於硬體的運行速度。

2. Big-O 背後的數學

為了理解演算法是如何增長的，我們使用一些數學函數。你不需要成為數學天才，只需要認出這些函數的「形態」即可：

• 線性函數： \( y = 2x \)（一條直線。如果輸入加倍，所需時間也加倍。）
• 多項式函數： \( y = 2x^2 \)（一條曲線。如果輸入加倍，所需時間會變成四倍！）
• 指數函數： \( y = 2^x \)（增長速度極其驚人。即使輸入很小，它也會「爆炸式」增長。）
• 對數函數： \( y = \log_{10} x \)（理想的狀態！隨著輸入增長，所需時間增加得非常緩慢。）

你知道嗎？集合的排列（Permutation）就是成員的一種排序方式。排列 \( n \) 個不同物件的方法數量是 \( n \) 階乘（\( n! \)）。例如，如果你有 3 本書，那麼排列它們的方法有 \( 3 \times 2 \times 1 = 6 \) 種。階乘的增長速度比指數函數還要快！

3. 複雜度順序（Big-O 符號）

Big-O 符號是一種用於描述演算法時間需求最壞情況（worst-case scenario）的速記法。它告訴我們該演算法的「複雜度順序」。

常見的 Big-O 排名（從最快到最慢）

1. 恆定時間 \( O(1) \)：無論輸入規模大小，所需時間始終相同。（例如：檢查清單中的第一個數字是否為偶數）。
2. 對數時間 \( O(\log n) \)：非常有效率。常見於「分治法（divide and conquer）」演算法，例如二分搜尋法（Binary Search）。
3. 線性時間 \( O(n) \)：時間隨輸入規模成正比增長。（例如：線性搜尋法（Linear Search））。
4. 多項式時間 \( O(n^2) \)：時間與輸入的平方成正比。常見於巢狀迴圈（nested loops）。（例如：氣泡排序法（Bubble Sort））。
5. 指數時間 \( O(2^n) \)：極其緩慢。將輸入規模加倍，所需時間會呈指數級增加。

如何推導複雜度：
觀察程式碼時，我們只關注增長最快的部分。如果一個程式包含線性部分和平方部分，我們稱其為 \( O(n^2) \)，因為當 \( n \) 變得非常大時，\( n^2 \) 部分才是真正起決定性作用的因素。

快速複習盒：
• \( O(1) \)：瞬間完成。
• \( O(n) \)：平穩增長。
• \( O(n^2) \)：快速增長。
• \( O(2^n) \)：危險的增長！

4. 計算的極限

儘管電腦每年的速度都在提升，但演算法複雜度和硬體限制仍然規定了我們能計算的極限。有些演算法太過複雜，即使在超級電腦上運行，所花的時間也會比宇宙的年齡還要長！

可處理問題與不可處理問題（Tractable vs. Intractable）

• 可處理問題（Tractable）：指可以在多項式時間（polynomial time）（\( O(n^k) \)）或更短時間內解決的問題。我們認為這些問題在合理時間內是「可做到的」。
• 不可處理問題（Intractable）：指沒有多項式時間解決方案的問題（它們可能是指數級的）。在技術上它們是「可解的」，但在 \( n \) 值很大時，實際上是不可能解決的。

啟發式方法（Heuristic Approach）：
當我們面臨不可處理的問題時，通常會使用啟發式（Heuristic）。這是一種「經驗法則」或「夠好就好」的方法。它可能無法給出 100% 正確的完美答案，但能在合理時間內給出一個令人滿意的答案。
例子：GPS 在擁有多達數百萬種路徑的城市中尋找「最佳」路線。它會使用啟發式方法快速找出一個非常好的路線，而不是計算每一條可能的路徑。

5. 停機問題（The Halting Problem）

是否有電腦完全無法解決的問題？有的！這些被稱為不可計算問題（non-computable problems）。

最著名的例子就是停機問題（Halting Problem）。
定義：停機問題詢問是否可以編寫一個程式，去檢查任何其他程式及其輸入，並判斷該程式最終會停止（halt）還是會陷入無限迴圈永遠執行下去。

定論：1936 年，艾倫·圖靈（Alan Turing）證明了停機問題是不可解的（unsolvable）。這樣的程式永遠不存在。
這為什麼重要？它證明了計算能力存在根本性的限制。有些問題是邏輯和電腦永遠無法回答的。

避免常見錯誤：不要混淆「不可處理（Intractable）」與「不可解（Unsolvable）」。
• 不可處理（Intractable） = 可解，但花費時間太長。
• 不可解（Unsolvable/Non-computable） = 電腦永遠不可能解決。

6. 圖靈機（Turing Machines）

圖靈機是一個電腦的理論模型。它幫助我們理解計算的極限。
它包含：
• 一組有限的狀態（finite set of states）（顯示在狀態轉換圖中）。
• 一個有限的符號字母表（finite alphabet）。
• 一條被劃分為方格的無限紙帶（infinite tape）。
• 一個可以在紙帶上一次移動一格的讀寫頭（read-write head）。

通用圖靈機（Universal Turing Machine）是一種可以模擬任何其他圖靈機的機器。它是現代電腦的理論基礎——單一台機器就能運行任何程式！

關鍵總結：圖靈機為「什麼是可計算的」提供了正式定義。如果圖靈機做不到，任何電腦也都做不到。

做得好！你已經完成了關於演算法分類的筆記。記住：效率的關鍵在於增長速度，而 Big-O 就是你衡量它的工具！