Classification of algorithms

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

嘿！這一章聽起來可能非常理論化，但實際上它是計算機科學中最實用的部分之一。為什麼呢？因為你正在學習如何在執行程式之前就先判斷出它的好壞！

我們將探索如何衡量演算法的效率——具體來說，就是當處理的數據量變得「巨大」時，它們的效能表現會如何。試想一下，這就像是預測當數百萬用戶同時登入時，你的應用程式是否會崩潰。這種分類演算法的能力，對於構建快速且可靠的軟體至關重要。

---

1. 比較演算法：效率至關重要 (3.13.5.1)

當我們比較兩種解決同一個問題（例如搜尋某個項目）的演算法時，我們不僅僅是問哪一個在少量數據下最快，我們更會問：「當問題規模增加時，它的表現如何？」

1.1 問題規模 (N)

分析演算法時的核心概念就是問題規模 (size of the problem)，通常以變數 \(n\) 表示。

例子： 如果你正在搜尋一個清單，\(n\) 就是該清單中項目的數量。如果你正在排序一個陣列，\(n\) 就是待排序元素的數量。

1.2 效率的維度

演算法通常透過以下兩個主要方式進行比較：

時間效率（時間複雜度）

這指的是演算法完成任務所需的時間量。關鍵在於，我們是透過計算執行的步驟或操作數量來衡量，而不是時鐘上的實際秒數（因為那取決於電腦的速度）。

• 我們關注的是操作數量相對於 \(n\) 的增長方式。

空間效率（空間複雜度）

這指的是演算法執行時所需的記憶體（儲存空間或資源）量。

• 一個非常高效的演算法會將完成任務所需的額外記憶體降至最低。

重點總結： 高效的演算法是指那些運行速度快（低時間複雜度）且使用最少額外記憶體（低空間複雜度）的演算法，特別是在輸入規模 \(n\) 增加時。

---

2. 複雜度級別與 Big O 標記法 (3.13.5.2)

Big O 標記法是我們用來表達演算法效能如何隨問題規模 (\(n\)) 增加而擴展的語言。它專注於增長率 (growth rate)，忽略了微小的細節和常數。

如果這看起來很數學化，別擔心——我們專注於理解整體趨勢就好！

2.1 理解增長率

以下是基本的 Big O 分類，按從最快（最好）到最慢（最差）排序：

1. 常數時間：\(O(1)\)

• 無論輸入規模 \(n\) 為何，執行時間均保持不變。

• 類比： 檢查隊伍中第一輛車的顏色。無論隊伍是有 10 輛車還是 10,000 輛，所花的時間總是一樣的。

• 例子： 使用索引存取陣列中的元素。

2. 對數時間：\(O(\log n)\)

• 執行時間增長得非常緩慢。當演算法反覆將問題空間減半時，就會出現這種情況。

• 類比： 在字典中查單字。你不會從第一頁開始翻，而是大約從中間打開，立即消除了半本書的範圍。

• 例子： 二分搜尋法 (Binary Search)。

3. 線性時間：\(O(n)\)

• 執行時間與輸入規模 \(n\) 成正比增長。

• 類比： 在書架上尋找一本放錯位置的書。你必須檢查每一本書，直到找到為止。

• 例子： 線性搜尋法 (Linear Search)，對清單進行一次遍歷。

4. 多項式時間：\(O(n^a)\)

• 執行時間增長迅速，通常表示為 \(O(n^2)\)（平方時間）。

• 這通常發生在演算法使用巢狀迴圈時，即對於每一個項目 \(n\)，你都要對所有 \(n\) 個項目執行另一次操作。

• 例子： 氣泡排序法 (Bubble Sort)。

5. 指數時間：\(O(a^n)\)

• 執行時間增長得非常快——即使對於中等大小的 \(n\)，這種速度也變得不可行。

• 此類別中的演算法通常只適用於非常小的輸入。

2.2 最好情況與最差情況的複雜度

演算法的複雜度可能會根據輸入數據而發生巨大變化。我們定義了兩種主要場景：

• 最差情況複雜度 (Worst-Case Complexity)： 這是演算法對於任何大小為 \(n\) 的輸入所需的最大時間。這通常是最重要的衡量指標，因為它為你提供了保證。
• 最好情況複雜度 (Best-Case Complexity)： 這是演算法所需的最少時間。這通常發生在數據已經完美排列時（例如，你要搜尋的項目剛好是第一個元素）。

例子：氣泡排序法的效率

氣泡排序法比較相鄰元素並進行交換。比較的次數很大程度上取決於清單的排序程度：

• 最差情況： 清單順序完全相反。需要進行多次比較和交換。時間複雜度為 \(O(n^2)\)。
• 最好情況： 清單已經排序完畢。高效版本的氣泡排序法會檢查某次遍歷中是否進行了交換，如果沒有，則停止。時間複雜度為 \(O(n)\)。

2.3 標準演算法的複雜度（必備知識）

你必須掌握這些關鍵演算法的最好和最差時間複雜度：

演算法	最差時間複雜度	最好時間複雜度
線性搜尋法	\(O(n)\)（項目在最後或不存在）	\(O(1)\)（項目是第一個元素）
二分搜尋法	\(O(\log n)\)	\(O(1)\)（項目是中間元素）
氣泡排序法	\(O(n^2)\)	\(O(n)\)（清單已排序）
合併排序法 (Merge Sort)	\(O(n\ \log n)\)	\(O(n\ \log n)\)
戴克斯特拉演算法 (Dijkstra)	\(O(n^2)\) （視乎實作方式可能更好）	\(O(n^2)\)
搜尋二元搜尋樹 (BST)	\(O(n)\)（如果樹的結構很差/呈線性）	\(O(\log n)\)（如果樹是平衡的）

重點總結： Big O 標記法根據增長率對演算法進行分類。對數、線性和高效的多項式演算法通常被認為是好的。像合併排序法（總是 \(O(n\ \log n)\)）這樣的排序演算法比氣泡排序法（最差 \(O(n^2)\)）要高效得多。

---

3. 演算法問題的分類 (3.13.5.3)

根據時間複雜度，我們可以對問題本身進行分類。

3.1 可處理問題 (Tractable Problems)

如果存在一個能以多項式時間或更短時間解決問題的演算法，該問題就是可處理的。

• 這包括 \(O(1)\)、\(O(\log n)\)、\(O(n)\) 和 \(O(n^a)\)（其中 \(a\) 為常數，如 \(O(n^2)\) 或 \(O(n^3)\)）。
• 可處理問題被認為是電腦可以實際解決的，即使面對大型輸入也是如此。

3.2 難處理問題 (Intractable Problems)

如果沒有已知的演算法能在多項式時間內解決該問題，該問題就是難處理的。

• 這些問題通常需要指數時間，如 \(O(2^n)\)。

雖然從技術上講是可以解決的（可計算的），但對於大的 \(n\) 值，它們實際上是無法解決的，因為所需時間會變得長到天文數字（例如搜尋一個巨大數據集中所有可能的組合）。

3.3 應對難處理問題：啟發式方法 (Heuristics)

由於我們無法在合理時間內為難處理問題找到完美解，我們通常使用啟發式方法。

啟發式方法是一套關於問題領域的規則或知識，有助於找到一個「足夠好」的解，即使它不是數學上的完美解。

啟發式方法可能會：

• 找到問題的近似而非最佳解（例如，找到一條快速路線，但不一定是絕對最快的一條）。
• 更改部分問題約束以使其能更快地求解。

例子： 旅行推銷員問題（尋找訪問多個城市的最短路線）是難處理的。啟發式方法可能涉及使用貪婪法——總是選擇最近且尚未訪問的城市作為下一個目標——這能提供一條不錯的路線，但可能不是絕對最短的。

重點總結： 可處理問題可以高效解決（多項式時間內）。難處理問題需要太多時間（通常是指數時間），因此我們經常訴諸啟發式方法來尋找快速的近似解。

---

4. 可計算與不可計算問題 (3.13.5.4)

現在我們不再討論單純的「慢」（難處理），而是轉向電腦根本無法解決的問題。

4.1 停機問題 (The Halting Problem)

停機問題是不可演算法解決問題中最著名的例子。

定義： 停機問題問的是：是否可能建立一個通用演算法，給定任何任意程式及其輸入，就能判斷該程式最終會停止（停機）還是會陷入無限迴圈持續運行，且無需執行該程式。

艾倫·圖靈 (Alan Turing) 的關鍵發現是：這個問題是不可解決的。不存在這樣的通用演算法。

4.2 對計算的意義

停機問題展示了計算的理論極限。

• 它證明了有些問題是電腦無法解決的，無論電腦有多快或你等多久。
• 它定義了什麼是可計算的（可透過演算法解決，如排序）以及什麼是不可計算的（如停機問題）。

你知道嗎？ 證明停機問題不可解決的理論，是基於一種稱為「反證法」的方法，表明如果存在這樣的程式，就會導致邏輯上的不可能。

重點總結： 停機問題是不可計算的。它證明了電腦不能透過演算法解決所有問題，這為軟體所能達成的目標設定了根本性的極限。

---

章節總結：分類回顧

理解這些分類有助於你選擇合適的工具。你需要的是一個在壓力下表現良好的演算法（低 Big O 複雜度）。

• 效率： 相對於輸入規模 \(n\)，以時間（步驟）和空間（記憶體）衡量。
• Big O： 描述效率的增長率（\(O(1)\) 是最好的，\(O(n^a)\) 是可以接受的，\(O(a^n)\) 通常非常糟糕）。
• 可處理問題： 可在多項式時間或更短時間內解決（例如合併排序法）。
• 難處理問題： 可以解決，但需要指數時間，對於大型輸入來說不切實際（通常需要啟發式方法）。
• 不可計算問題： 根本無法透過任何演算法解決（例如停機問題）。

繼續練習追蹤那些簡單的演算法，以理解它們的操作如何與 \(n\) 相關聯！