# Algorithm Design

笛卡兒二元論當作比喻，說明 **演算法（algorithm）** 與 **硬體／軟體（hardware / software）** 在電腦世界中的分工與本質。可以分成幾個段落來看：

| 段落 | 核心概念 | 說明 |
| ------------------- | ------------------------------------------------------------------------ | -------------------------------------------------------- |
| 1. 引笛卡兒 | 心靈（mind）與身體（body）是兩種截然不同的「實體」 | 笛卡兒認為兩者性質迥異但能互動。作者先搬出這個哲學概念，為的是後面要談電腦世界的「抽象邏輯」vs.「物理載體」。 |
| 2. 為何先談哲學？ | 二元論讓我們更容易理解「演算法與其他人類發明的不同之處」 | 把演算法看成心靈、把硬體看成身體，能凸顯演算法的抽象、不滅與通用特性。 |
| 3. 電腦史上的分水嶺 | **硬體**是看得見摸得到的機械零件；**軟體**是程式化、形式化的問題解（solution） | 先有「把問題寫成數學表示」這個想法，才催生電腦；而硬體只是負責執行軟體的「肉身」。 |
| 4. 兩者根本差異 | 硬體受物理定律約束、會老化故障；軟體受數學邏輯約束、**本質上不會壞** | 這裡直接對應笛卡兒的「身體會死亡、心靈不朽」。 |
| 5. 什麼是演算法？ | 演算法是一組**抽象**且**可重現**的步驟與規則 | 用任何程式語言（Python、C++、組合語言……）實作，只要遵守同一邏輯就會得到同樣結果。 |
| 6. 比喻——食譜與樂譜 | 食譜／樂譜都是「計畫 (plan)」的具體化：步驟、份量、節拍… | 不管用哪種廚房、哪把琴，照著譜（＝演算法）就能烹飪／演奏出相同作品。 |
| 7. 好食譜的特質 → 好演算法的特質 | - 量化、抽象 (quantitative & abstract)<br>- 與特定廚房/器材無關 (platform-independent) | 影射演算法應該有的可移植性與精確性；自然語言描述往往不夠精確，易生歧義。 |

### 小結

* **硬體**＝物理世界、會耗損；**軟體／演算法**＝數學世界、可永續複製。
* 笛卡兒的二元論提供了一個直觀框架，幫助我們理解為何演算法（心靈）與硬體（身體）分離能帶來強大威力。
* 演算法的價值在於其抽象與可重複：一次設計，處處實現，這也是它成為電腦科學核心概念的原因。

以下把這一跨頁內容拆成三個區塊來說明，方便你快速抓重點與脈絡：

---

## 1️⃣　「好演算法」的四大特質

書中把 **食譜／樂譜** 比喻成演算法後，歸納出一套「評鑑演算法好壞」的通用標準：

| 特質 | 說明 | 實務意義 |
| --------------------------------------------------- | ----------------------------- | ------------------------------------------------ |
| **Programmer Independence**<br>（程式設計者獨立） | 不論哪位工程師實作，都應得到同樣的正確結果、消耗近似的資源 | 代表演算法規格應該清晰、完整，不能靠「開發者個人臨場智慧」補洞 |
| **Hardware Independence**<br>（硬體獨立） | 換成不同 CPU、記憶體或作業系統時仍能保持相近行為 | 演算法越不依賴底層硬體特有指令，就越容易遷移、擴充 |
| **Abstraction & Clarity**<br>（抽象與明確） | 邏輯必須無歧義、可被任何人讀懂並實作 | 模糊描述 ⇒ 多版本、難維護。良好抽象 ⇒ 易於單元測試、驗證 |
| **Quantifiable Correctness & Cost**<br>（可量化的正確性與成本） | 輸出要可驗證；時間與空間成本要可度量 | 方便在不同演算法之間做 **比較 (benchmark)** 和 **優化 (tuning)** |

---

## 2️⃣　可計算 (computable) vs. 不可計算 (non-computable)

* **演算法 = 可被邏輯步驟「系統化」解決的方法**。
* 若一個問題可以轉化為有限的數學／邏輯步驟，就屬於 **computable problem**（可計算）。
* **Halting Problem（停機問題）**——Alan Turing 證明：**不存在**一個通用演算法能判斷「任意程式+輸入」最終會停還是永遠執行。這是經典的 **non-computable problem**，用來提醒我們：

* 不是所有問題都找得到演算法解。
* 研究演算法前，先判斷問題是否「可計算」很重要。

---

## 3️⃣　演算法設計中的兩大路線：Algorithmic Method vs. Heuristic Method

> 書後面第 10 章會詳細討論，這裡先把結論提要出來。

| 面向 | **Algorithmic Method** | **Heuristic Method** |
| -- | ---------------------------------------------------- | ------------------------------------ |
| 定義 | 嚴謹、結構化的步驟，**保證**在有限時間內給出正確（或最佳）解 | 基於經驗、直覺或常識的「捷徑」；通常**更快**，但不保證最優或一定成功 |
| 優點 | 可預測、可重複，適用於需高準確度的場景（例如加密、金融結算） | 快速、省資源，適用於資料龐大或即時決策（例如搜尋引擎排名、遊戲 AI） |
| 缺點 | 可能計算量大、實作複雜 | 可能只給近似解，且結果品質難以嚴格證明 |
| 關係 | **互補**而非對立。許多系統會先用 heuristic 找到「不錯」的範圍，再用嚴謹演算法精修或驗證。 | |

---

## 4️⃣　為何還要做「演算法分析」？

1. **硬體再強，也需要好演算法**

* GPU、SSD、雲端計算帶來龐大算力，但寫得差的演算法仍可能在大資料面前崩潰。
2. **正確性**

* 用嚴謹的數學證明（或反例）確保演算法在所有輸入上都正確。
3. **效率**

* 透過時間複雜度 *T(n)*、空間複雜度 *S(n)* 的量化比較，找出最適合實務限制的方案。
4. **可預測性 & 可擴充性**

* 知道演算法在資料量增加 10×、100× 時的行為，才能做容量規劃。
5. **激發創新**

* 很多 AI/ML、電腦視覺的突破，其實來自演算法（模型、訓練技巧）革新，而非單純硬體升級。

---

### 🔑 讀後重點

* **定義問題 → 確定可否用演算法解 → 選擇嚴謹或啟發式方法 → 分析正確性與複雜度**，是學習與設計演算法的基本流程。
* 即便計算資源日益便宜，「演算法思維」仍決定系統最終的效能上限與可維護性。

---

## 1️⃣　為何還要在「硬體飛快進步」的今天學演算法分析？

| 理由 | 一句話重點 | 現場工程意義 |
| ----------------------------------- | ----------------- | ------------------------------------------------------------------------- |
| **Algorithm efficiency** | 同樣功能，選對演算法可省時省記憶體 | 例如：百萬筆資料排序，用 `O(n log n)` 的 merge-sort 取代 `O(n²)` 的 bubble-sort，可從數小時降到數秒 |
| **Better problem-solving skills** | 拆問題、抽象化 → 找到最優步驟 | 影響不只寫程式，設計系統、排產等都通用 |
| **Understanding limitations** | 知道哪些問題「算不動／算不得」 | 如停機問題、NP-complete 問題，提前評估方案可行性或改用近似／啟發式 |
| **Preparing for future challenges** | 資料量只會更大、場景更複雜 | 擁有分析基礎才能持續優化，跟上 AI、IoT、大數據的需求 |

---

## 2️⃣　思想實驗：**無限算力 vs. 精良演算法**

> 書中舉例：假設 CPU 無敵快、記憶體無上限，把長度 `n` 的陣列「列舉所有 `n!` 排列」再檢查是否有序——理論可行，但 `O(n!)` 不符實務。
> 即便在「算力無上限」的科幻場景，熟悉演算法分析仍能幫你 **從暴力解 → `O(n²)` → `O(n log n)`** 持續優化；真正落地時差距更大。

---

## 3️⃣　四大經典求解策略 & 何時用？

| 方法 | 核心思路 | 優點 | 侷限 / 典型例題 |
| -------------------------------- | ---------------- | ----------------------------------------- | --------------------------------------------------- |
| **Sequential / Straightforward** | 一連串指令直推到底 | 易懂、易除錯 | 複雜度高，難應付巨量資料<br>例：線性掃描找最大值 (`O(n)`) |
| **Divide-and-Conquer** | 切小問題 → 各自解 → 再合併 | 常見 `T(n)=aT(n/b)+f(n)` ，多數可達 `O(n log n)` | 轉換＋合併需額外成本；不是所有問題都能拆<br>例：Merge Sort、Quick Sort、FFT |
| **Dynamic Programming** | 子問題重疊 + 記錄結果 | 把指數爆炸降到多項式 | 需「最優子結構」＆「重疊子問題」兩性質<br>例：最短路徑 (DAG)、背包、多序列比對 |
| **Greedy Algorithms** | 每一步取當下最划算 | 簡單實作、常線性～`O(n log n)` | 不保證全域最優；須證明「貪婪選擇性」<br>例：活動排程、最小生成樹 (Kruskal/Prim) |

＞ **比較演算法** 時，書中特別強調以 **時間／空間成本** 為首要指標，並在後面各章深入實務案例。

---

## 4️⃣　二元評估目標：**效率 (Efficiency) × 正確性 (Correctness)**

1. **正確性**

* **Termination** — 必須在有限步驟內結束，不能陷入無窮迴圈。
* **Validity** — 對所有合法輸入都輸出「符合規格」的結果。

> ▶︎ 典型工作：用循環不變式、數學歸納或 Hoare Triple 證明。

2. **效率**

* **時間複雜度** `T(n)` — 量測指令／比較／記憶體訪問次數。
* **空間複雜度** `S(n)` — 額外佔用記憶體。

> ▶︎ 典型工作：建立迴圈計算式或遞迴式，再化簡到 Big-O。

只有同時滿足「**正確**且**高效**」才算設計出卓越演算法；若二選一失衡，實務上都難以採用。

---

### 📌 實戰 Tips

1. **先證正確後談效率**：否則易陷入「優化 Bug」。
2. **實際量測 vs. Asymptotic**：大 O 給趨勢；實務還需跑 benchmark 抓常數與 cache 行為。
3. **Know your toolbox**：遇新問題先判斷能否套用上述 4 策略；沒有就考慮啟發式或近似法。

---

## Ⅰ · 正確性（Correctness）

### 1. 為何「跑很多測試」仍不足以證明正確？

* **反例 (counter-example)** 的存在：只要有一筆輸入能讓演算法出錯，就能推翻「經過大量測試皆正確」的主張 ⇒ 測試只能增加信心，無法下定論。

### 2. 形式化證明的兩大工具

| 技法 | 核心概念 | 典型應用 |
| -------------------------- | -------------------------------------------- | ------------------- |
| **數學歸納 (inductive proof)** | 先證最小規模 (base case)，再假設 `n=k` 正確推得 `n=k+1` 正確 | 歸納排序演算法、遞迴函式 |
| **迴圈不變式 (loop invariant)** | 找到在每次迴圈前後都成立的條件，證明初始化→保持→終了皆滿足 | 插入排序、selection sort |

> 書中預告：第 2 章會深入「如何寫出並驗證這些證明」。

---

## Ⅱ · 效率（Efficiency）

### 1. 核心量測指標

| 指標 | 問題 | 為何重要 |
| ---------------- | ------------------------------ | ---------------------- |
| **時間複雜度** `T(n)` | 隨輸入規模 `n` 增長，所需運算步驟或 CPU 時間怎麼變 | 決定可否在時限內完成任務 |
| **空間複雜度** `S(n)` | 執行期間額外耗用多少記憶體 | 影響能不能跑在手機、嵌入式或記憶體吃緊的場景 |

> 解析工具：**漸近分析 (asymptotic analysis)**——Big-O、Θ、Ω 等符號設定「上／下／精確」界線，讓不同演算法能在理論層面做比較。
> 第 3 章會專門介紹這套數學語言。

### 2. 其他現代環境要考慮的效率維度

| 維度 | 典型情境 |
| ------------- | ---------------------------- |
| **電池與能源** | 行動裝置、穿戴式 |
| **資料傳輸/網路耗用** | 邊緣運算、頻寬受限應用 |
| **雲端成本** | Serverless、外部 API / GPU 付費使用 |
| **人工標註成本** | AI/ML 流程中的人力介入（資料清洗、驗證） |

雖然本書聚焦「時間 & 空間」，作者提醒讀者：真實專案裡常需把上述因素納入總體效率評估。

---

## Ⅲ · 章節小結

1. **本章回顧**

* 演算法是抽象問題解，與硬體分離（呼應前面笛卡兒二元論比喻）。
* 為了選擇/設計好演算法，必須同時檢驗 **正確性** 與 **效率**。

2. **接下來的學習路徑**

* **第 2 章**：各式正確性證明方法的細節與範例。
* **第 3 章**：漸近符號與理論基礎，鋪陳後續複雜度比較與優化分析工具。

> 換句話說，本章相當於 **演算法分析學科的「導覽地圖」**：先定義終點（正確 & 高效），再指出必經的兩條主幹道（形式化證明 + 漸近分析），為後面深入各類演算法奠定基礎。

---

## 第 2 章開宗明義：用「數學化」手段保證演算法正確

| 區塊 | 重點 | 說明 / 拓展 |
| ----------------------------------------------------------------------------- | ------------------------------------------------------------------------------- | ------------------------------------- |
| **章名**<br>Mathematical Induction and Loop Invariant for Algorithm Correctness | 兩大工具：<br>1. **數學歸納法** (Mathematical Induction)<br>2. **迴圈不變式** (Loop Invariant) | 目的：教你如何對演算法做「形式化正確性證明」，而不只是靠單元測試。 |
| **笛卡兒引言** | “With me, everything turns into mathematics.” | 強調：電腦科學的核心（演算法設計與驗證）最終都要回到嚴謹的數學基礎。 |
| **本章範圍敘述** | - 揭示數學歸納在建立迴圈不變式時的關鍵角色<br>- 透過「詳細範例」示範這兩個概念如何合作驗證演算法 | 提醒：除了理論，也會給實務技巧，讓你在後續章節能親手為程式寫出正確性證明。 |

---

#### 1. 反例 (counterexample) 與間接證明 (indirect proof)

* 找到 **一筆輸入就能讓演算法出錯** ⇒ 立即推翻「此演算法對所有輸入都正確」的宣稱。
* 這種方法簡潔有力，常被稱作 **反證法** 或 **間接證明**。
* 但若反例難尋，就必須改走「直接證明」路線。

> **Example 2.1**
> 命題：對所有 `a > 1`、`b > 1`，有 `(a + b)! = a! · b!`?
> *反例*：取 `a = 2`, `b = 3` ⇒ `5! = 120` ≠ `2!·3! = 12` ⇒ 命題為假。
> → 示範如何用單一 counterexample 迅速駁斥錯誤命題。

---

#### 2. 數學歸納法 (direct proof) 的必要性

* 當反例找不到或命題被猜測為 **真** 時，需要「對所有自然數 n 都成立」的 **直接證明**。
* 歸納法步驟：

1. **Base Case**：證明最小 n（通常是 0 或 1）時命題為真。
2. **Inductive Step**：假設 n=k 時成立，推得 n=k+1 時也成立。
* 在演算法語境裡，`n` 常代表「輸入規模 / 迴圈次數 / 遞迴深度」，歸納法可證明演算法在所有規模下皆正確完成。

---

#### 3. 迴圈不變式──讓「程式碼」說服數學

* **Loop Invariant**：在每次迴圈開始前即為真，並且經過迴圈本體後仍為真的敘述。
* 證明模式 = 歸納法在程式層面的具體化：

1. **Initialization**（對應 Base Case）
2. **Maintenance**（對應 Inductive Step）
3. **Termination**（當迴圈結束可推得演算法達成目標）
* 多用於排序演算法（Insertion Sort）或資料結構迭代（Heapify）等範例。

---

### 透視本章：學完可做什麼？

1. **辨識錯誤聲稱**：看到「跑了很多測試所以沒問題」時，能立即質疑「那只是不完全證明」。
2. **寫出形式化證明**：對自己的或同事的演算法，能用歸納法 + 不變式給出無懈可擊的正確性保證。
3. **為後續章節奠基**：接下來內容會用這些工具剖析各類演算法——若概念打底不足，後面會看得吃力。

---

## 1. Flashback：數學歸納法 (Mathematical Induction) 的歷史與核心

| 重點 | 說明 |
| ------------ | ---------------------------------------------------------------- |
| **歷史** | 可追溯至 3000 多年前；古希臘數學家已用此技巧證明等差級數、圖案數列等性質。 |
| **原理** | **若命題在範圍邊界 (base case) 成立，且能從 n ⇒ n + 1 推得命題仍成立，那麼命題對所有 n 均成立**。 |
| **為何適用演算法？** | 演算法的「輸入規模 n」正好是自然數序列；使用歸納法能保證程式在所有可能輸入規模下皆正確。 |

---

## 2. 歸納法兩步驟 + 範例 2.2

### 2.1 歸納流程

1. **Base Case（初始步）**

* 驗證 n = 0 或 n = 1 時命題為真。
2. **Induction Step（遞推步）**

* 假設 n = k 時命題為真（歸納假設），證明 n = k + 1 亦為真。
* 完成後即可推論命題對 **所有** 自然數 n 成立。

> 在演算法情境裡，base case 相當於「最小輸入」；遞推步則象徵「規模擴大一單位時，仍維持正確」。

### 2.2 Example 2.2：首 n 個自然數和

> 要證明
>
> $$
> 1 + 2 + 3 + \dots + n \;=\; \frac{n(n+1)}{2}
> $$

* **Base Case (n = 1)**
左邊 = 1，右邊 = 1·2 / 2 = 1 → 成立
* **Induction Step**
假設 k 項和為 k(k + 1)/2
則

$$
1 + 2 + \dots + k + (k+1)
= \frac{k(k+1)}{2} + (k+1)
= \frac{k(k+1) + 2(k+1)}{2}
= \frac{(k+1)(k+2)}{2}
$$

即對 n = k+1 也成立。
∴ 命題對所有 n 成立。

---

## 3. 歸納法 ↔️ 演算法正確性

1. **演算法結構 = 指令序列**

* 類比「食譜」：一串步驟組合而成。
* 書中把指令分兩級：

* **Simple Commands**（與輸入無關，如常數指派 `x = 0`）
* **Compound Commands**（內含其他指令的區塊）

* **Selections**：`if–then–else` 等條件分支
* **Iterations**：`for / while` 迴圈（下一頁繼續討論）

2. **為何需要形式化證明？**

* **Counterexample 容易打臉**：跑再多測試，只要漏掉一筆特殊輸入就可能失敗。
* **歸納法 + 迴圈不變式** 提供「涵蓋所有 n」的保證，尤其對迴圈／遞迴演算法至關重要。

3. **實務 Tips**

* 撰寫迴圈前，先思考「每次迴圈開始前應滿足的條件」—> 這就是 **Loop Invariant**。
* 透過 *Initialization–Maintenance–Termination* 三步，將迴圈不變式寫成歸納證明，可確保程式邏輯萬無一失。

---

### 🔑 小結

* 本節示範了 **數學歸納法** 的標準模板，並說明它在演算法驗證中的角色。
* 接下來書中會把歸納法應用到 **迴圈不變式** 的建立，進一步實務地證明迴圈／遞迴演算法的正確性。
* 掌握這套方法，你就能從「大量測試」升級到「形式化保證」，大幅提升程式可靠度與說服力。

---

**把「數學歸納」轉譯成程式世界可用的檢驗工具——迴圈不變式 (loop invariant)**，並用「**二分搜尋**」當範例走一遍流程。可分四部分來看：

## 1. 迴圈（iteration）是演算法的「引擎」

| 類比 | 說明 |
|------|------|
| **車體 vs. 引擎** | 簡單指令 = 車身固定零件；選擇 (if/else) = 方向盤；**迴圈** = 引擎帶動前進。<br>演算法的正確性與成本，很大部分取決於這顆「引擎」是否可靠、有效率。 |
| **數學歸納 ↔ 迴圈** | 歸納法驗證「走第 k 步正確 ⇒ 第 k+1 步也正確」。對迴圈來說就是：若每次迴圈開始時條件成立，執行一輪後仍成立，則可保證一直成立到結束。 |

---

## 2. 二分搜尋程式碼拆解

def binary_search(ar, x):
    low = 0
    high = len(ar) - 1
    while low <= high:
        mid = (high + low) // 2
        if ar[mid] < x:
            low = mid + 1
        elif ar[mid] > x:
            high = mid - 1
        else:
            return mid

| 區塊 | 角色 | 關鍵點 |
|------|------|--------|
| **Simple commands** | `low = 0`, `high = len(ar) - 1` | 與輸入大小無關，設定初始邊界；在迴圈前執行一次。 |
| **Iteration block** | `while low <= high:` | 只要搜尋區間還沒空，就持續縮小範圍 ⇒ 正確性與終止性核心。 |
| **Selection block** | `if / elif / else` | 依 `ar[mid]` 與 `x` 比較調整 `low` 或 `high`，或在命中時回傳。 |

> **成本 (下一章細談)**：每次迭代把範圍減半，因此時間複雜度 = `O(log n)`。

---

## 3. 為何只靠歸納還不夠？——引入 *Loop Invariant*

- 歸納法本身 **不含「演算法一定結束」的驗證**。
- 在程式裡，我們需要同時確定：
1. 進入迴圈前條件成立（Initialization）
2. 每個回合後條件仍成立（Maintenance）
3. 迴圈結束時條件 + 迴圈終止判斷 ⇒ 得到最終正確結果（Termination）

這就形成了「**迴圈不變式證明三步曲**」，可視為「為演算法特製的歸納法」。

---

## 4. 數學歸納 vs. 迴圈不變式 —— 對照表

| **數學歸納 (Mathematical induction)** | **Loop Invariant 證明步驟** | 功用 |
|---------------------------------------|-----------------------------|------|
| Base case | **Initialization** | 迴圈開始前先建立不變式的真實性 |
| Induction step | **Maintenance** | 證明：若回合開頭不變式成立 → 回合結尾仍成立 |
| *(無對應)* | **Termination** | 當迴圈條件失效 (e.g. `low > high`) 時，不變式仍成立，並能推導最終答案正確 |

> 📌 **Termination** 是程式特有需求：保證「不會跑無限迴圈」。
> 在二分搜尋中，不變式可設為：
> `x` 若存在，必定落在索引區間 `[low, high]`。
> 初始化：`low=0`, `high=len-1` → 命題真。
> 維持：每次比較後縮小區間仍涵蓋目標。
> 終止：`low > high` 時目標不存在；或 `ar[mid]==x` 時正確回傳索引。

---

### ✦ 實務 Takeaway

1. **寫迴圈先寫不變式**：先想清楚「每一輪必須保持的事實」，再寫程式比 debug 省力。
2. **驗證三步驟**：初始化 → 維持 → 終止，缺一不可。
3. **成本分析靠迴圈結構**：像二分搜尋的「每輪減半」直接帶出 `log n` 複雜度。

掌握迴圈不變式，你就能把抽象的數學歸納真正落地到每一段迴圈／遞迴程式，給出嚴謹且說服力十足的正確性證明。

---
**「迴圈不變式三步驟」** 說得更具體，並強調 **「迴圈條件」(loop condition) 與「迴圈不變式」(loop invariant) 的差別**。核心重點整理如下：

## 1. 迴圈不變式的三步驟（再次複習）

| 步驟 | 用途 | 要做到的事 |
|------|------|-----------|
| **Initialization** 起始 | 迴圈第一次執行前，不變式要成立 | 等同數學歸納法的 base case |
| **Maintenance** 維持 | 每次進入迴圈→執行迴圈體→離開迴圈前，不變式仍要成立 | 等同歸納法的 induction step |
| **Termination** 終止 | 迴圈結束後（條件為假），不變式仍成立，並且能推出演算法得到正確結果 | 這一步是純粹的數學歸納裡*沒有*、但程式必須有的 |

---

## 2. 校車接學生的比喻（Example 2.3）

> **不變式**：車上學生人數「只增不減」。

| 三步驟對應 | 校車場景描述 |
|------------|-------------|
| **Initialization** | 起點出發時車上 0 人，符合「只增不減」。 |
| **Maintenance** | 每到一站只上車、不下車 → 人數要嘛增加、要嘛不變 ⇒ 不變式持續為真。 |
| **Termination** | 抵達學校後不再有學生上下車，但人數依舊 ≥ 初始人數 → 不變式依舊成立，故流程正確完成。 |

> 透過此日常場景，作者想讓讀者直觀感受「一個在整趟流程中始終不變的條件」如何幫助我們確認系統行為正確。

---

## 3. Loop Condition ≠ Loop Invariant

| 對象 | 例子（Binary Search） | 作用 | 為何它 **不是** 不變式？ |
|------|----------------------|------|---------------------------|
| **Loop Condition** | `low <= high` | 控制「要不要再跑下一圈」 | 只在 *進入迴圈前* 需要為真，跳出時必為假；它不需在整個執行過程一直保持。 |
| **Loop Invariant** | 若 `x` 存在，**必定**位於 `[low, high]` | 驗證演算法正確性 | 必須在 **迴圈開始前、每次迴圈結束後，以及迴圈完全結束後** 都為真；涵蓋整個生命周期。 |

> - **有效性範圍不同**：
> *條件* 只負責「什麼時候停」，而 *不變式* 負責「不論跑了多少圈，核心事實都沒被破壞」。
> - **用途不同**：
> 迴圈條件偏向*流程控制*；迴圈不變式是*正確性證明*的工具。

---

## 4. 為什麼要分清這兩者？

1. **避免誤解**：把 loop condition 當不變式容易導致錯誤的「證明」，因為條件在跳出後變成 *false*。
2. **寫測試更精準**：知道不變式後，你能在單元測試裡針對每次迴圈迭代驗證其成立，而不只是驗終點結果。
3. **Debug 更高效**：當輸出錯誤時，檢查哪一步破壞了不變式，比盲目打 log 更快定位 bug。

---

### ✦ Takeaway

- **迴圈條件**＝讓程式知道「該不該繼續跑」。
- **迴圈不變式**＝讓你\我\任何讀者知道「不管跑幾圈都不會出錯」。
- 先寫出好的不變式，才能在 Initialization、Maintenance、Termination 三關立下「保證書」，把正確性鎖死；這是大型或關鍵系統（例如金融、航太）必備的程式設計習慣。

---

## 1. Loop Condition 與 Loop Invariant 再對比

| 角色 | 作用 | 在二分搜尋中的例子 |
| ------------------------------ | ------------------------------------------------ | ------------------------------------------------------------- |
| **Loop Condition** <br>(迴圈條件) | 決定「要不要再跑下一圈」。是一種**流程控制**機制；<br>本身**不保證**演算法邏輯正確。 | `low <= high` —— 只要還有範圍要搜尋就繼續迭代；<br>當 `low` 超過 `high` 時跳出迴圈。 |
| **Loop Invariant** <br>(迴圈不變式) | 必須在**每一次**迴圈開頭與結尾都成立，用來**證明演算法正確**。 | 「如果目標值存在，必位於 `[low, high]` 區間內」。<br>每次比較後縮小區間仍保持此事實，保證不會漏掉答案。 |

> 作者強調：條件只負責「開/關」，不變式才是「品質保證」。

---

## 2. 章節摘要 (Summary)

* **先談數學歸納**

* 兩步：Base Case → Induction Step
* 用來證明命題對所有自然數皆成立。
* **再升級為迴圈不變式**

* 加入 **Termination**，確保迴圈最終停止且結果正確。
* 示範：以二分搜尋為例，具體演練 Initialization／Maintenance／Termination。
* **重點結論**

* **正確性** 驗證 = 本章任務；
* **複雜度** 分析 = 下一章主軸。
* 建立這兩套方法論後，後續介紹的新演算法都會重複檢查不變式來確保可靠性。

---

## 3. 延伸閱讀 (References and further reading)

| 書名 & 出版社 | 為什麼值得讀？ |
| -------------------------------------------------------- | ---------------------------- |
| *Introduction to Algorithms* (CLRS, MIT Press 4/e 2022) | 經典「黑皮書」，理論 + 伪程式最完整的權威教材。 |
| *Algorithm Design* (Kleinberg & Tardos 2005) | 著重「設計思想」與範例拆解，適合搭配 CLRS。 |
| *The Art of Computer Programming* Vol. 1 (Knuth 1997) | 深度理論 + 程式範例，想鑽研底層可循序閱讀。 |
| *Algorithms Unlocked* (Cormen 2013) | CLRS 作者寫給入門者的輕量版。 |
| *Discrete Mathematics and Its Applications* (Rosen 2012) | 演算法分析需用到的離散數學基礎全收錄。 |
| *Concrete Mathematics* (Graham, Knuth 1994) | 進階組合數學、漸近分析利器。 |
| *How to Prove It* (Velleman 2019) | 系統化介紹「寫證明」技巧，對掌握歸納法與不變式很有幫助。 |

---

### 📌 讀完可以帶走的觀念

1. **條件控制 ≠ 正確性保證**：別把 `while` 條件當成不變式。
2. **三步曲**：Initialization → Maintenance → Termination；缺一不可。
3. 後續學習路線：先確保「對」、再追求「快」——下一章正式進入時間/空間複雜度的世界。