📗 演算法導論

🎯 什麼情境該想到我

當你想「嚴謹確認一個迴圈/演算法真的正確」，或迴圈邏輯容易出 off-by-one、難以推理時。

⚙️ 怎麼用（找出並驗證一條在迴圈中恆成立的性質）

1. 找不變式：一句在「每次迭代開始前都成立」的陳述（例：排序中「A[0..i-1] 已排好序」）。
2. 證三件事：
   • 初始化：第一次迭代前，不變式成立。
   • 保持：若某次迭代前成立，執行後（下次前）仍成立。
   • 終止：迴圈結束時，不變式 + 終止條件 → 推出「演算法正確」。

實務上，即使不寫形式證明，「在腦中維持一條不變式」也能讓你迴圈寫得更對、更少邊界錯誤。

🧪 我實際套用的紀錄

• 2026-07-15：（待填）

⚠️ 注意

• 不變式要選「強到能推出正確性、又真的每輪都成立」的那條——太弱沒用、太強不成立。

🔗 相關工具

• 工具-遞迴式與主定理 —— 姊妹工具，一個證正確性，一個算複雜度，配成一組看演算法
• 工具-系統化除錯 —— 實務用途，迴圈出 off-by-one 時用不變式定位是哪一輪開始不成立

🎯 什麼情境該想到我

當一個操作「偶爾很貴、多數很便宜」（如動態陣列滿了才擴容），你想算「一連串操作」的整體平均成本時。

⚙️ 怎麼用（三種方法擇一）

攤還分析算的是「一序列操作的總成本 ÷ 操作數」，而非單次最壞。

1. 聚合法（Aggregate）：直接算 n 個操作的總成本，再除以 n。
2. 記帳法（Accounting）：對便宜操作「多收費」存起來，用來支付未來昂貴操作。
3. 位能法（Potential）：定義一個位能函數，把成本變化攤到整個序列。

經典例：動態陣列 push——雖然擴容那次是 O(n)，但攤還到每次 push 是 O(1)。

🧪 我實際套用的紀錄

• 2026-07-15：（待填）

⚠️ 注意

• 攤還是「序列平均」不是「機率平均」——它保證的是總量上限，不靠輸入分布假設。

🔗 相關工具

• 工具-時間複雜度分析、工具-儲存引擎B-Tree與LSM-Tree（LSM compaction 的攤還成本）

🎯 什麼情境該想到我

當你有一個分治/遞迴演算法，想算它的時間複雜度（如「為什麼合併排序是 O(n log n)」）時。

⚙️ 怎麼用

1. 寫出遞迴式：T(n) = a·T(n/b) + f(n)（拆成 a 個大小 n/b 的子問題，合併成本 f(n)）。
2. 用主定理（Master Theorem）比較 f(n) 與 n^(log_b a)：
   • f(n) 較小 → T(n) = Θ(n^(log_b a))
   • 兩者同量級 → T(n) = Θ(n^(log_b a)·log n)（如合併排序 a=2,b=2 → n log n）
   • f(n) 較大（且規則）→ T(n) = Θ(f(n))
3. 主定理不適用時，用遞迴樹畫出來加總，或用代入法猜測並歸納證明。

🧪 我實際套用的紀錄

• 2026-07-15：（待填）

⚠️ 注意

• 主定理有適用前提（子問題等分、f(n) 行為規則）；不符時別硬套，改用遞迴樹。

🔗 相關工具

• 工具-時間複雜度分析 —— 上位工具，主定理是它在遞迴演算法上的專用解法
• 工具-演算法設計策略 —— 使用場合，凡是走分治路線的設計都要靠遞迴式算出代價
• 工具-迴圈不變式 —— 姊妹工具，一個算成本，一個證正確，兩者一起才算把演算法看完