Algorithms 演算法 - paulip114/blog GitHub Wiki
常見演算法（Algorithms）總整理
🧮 一、排序演算法（Sorting Algorithms）
| 演算法 | 時間複雜度 | 穩定性 | 適用情境 |
|---|---|---|---|
| Bubble Sort | O(n²) | ✅ | 教學用途、概念簡單 |
| Selection Sort | O(n²) | ❌ | 教學用途 |
| Insertion Sort | O(n²) | ✅ | 資料幾乎已排好（小規模） |
| Merge Sort | O(n log n) | ✅ | 穩定高效，適合大型資料集 |
| Quick Sort | 平均 O(n log n) / 最差 O(n²) | ❌ | 實務中非常常用，平均效能優異 |
| Heap Sort | O(n log n) | ❌ | 不需額外空間、實作優先順序排序 |
| Radix Sort | O(nk) | ✅ | 適合大量數字排序（如電話號碼、ID） |
🔍 二、搜尋演算法（Searching Algorithms）
| 演算法 | 時間複雜度 | 適用情境 |
|---|---|---|
| Linear Search | O(n) | 小資料集或無序資料 |
| Binary Search | O(log n) | 已排序的陣列 |
| Depth-First Search（DFS） | O(V + E) | 圖 / 樹搜尋、遞迴遍歷 |
| Breadth-First Search（BFS） | O(V + E) | 圖 / 樹搜尋、找最短路徑（不含權重） |
| Ternary Search | O(log n) | 單峰函數找最大/最小（進階） |
🧠 三、分治 / 遞迴（Divide & Conquer / Recursion）
| 技巧 | 說明 | 常見應用 |
|---|---|---|
| Divide & Conquer | 問題分小塊 → 解決 → 合併 | Merge Sort、Quick Sort、Binary Search |
| Recursion | 函數自己呼叫自己 | 樹遍歷、費氏數列、背包問題、子集 |
📦 四、貪婪演算法（Greedy Algorithms）
| 概念 | 說明 | 常見應用 |
|---|---|---|
| 每一步都選擇當前最好（局部最優） → 嘗試達成整體最優 | 結果不一定最優，但效率高 | |
| 應用範例 | - 活動選擇問題 |
- 最小生成樹（Kruskal、Prim）
- Huffman 編碼
- 換零錢問題（部分情況）|
📚 五、動態規劃（Dynamic Programming, DP）
| 概念 | 說明 | 常見應用 |
|---|---|---|
| 子問題 + 記憶化（Memoization） | 儲存重複子問題結果，避免重算 | 費氏數列、背包問題、最長公共子序列、剪繩子、找最大利潤 |
| 狀態轉移 | 根據前一狀態推導出目前狀態 | DP Table 或遞迴搭配 cache 實作 |
🌳 六、圖論演算法（Graph Algorithms）
| 演算法 | 說明 | 時間複雜度 | 適用情境 |
|---|---|---|---|
| BFS / DFS | 圖的基本遍歷 | O(V + E) | 尋找路徑、聯通區塊 |
| Dijkstra | 單源最短路徑（非負權重） | O(E log V) | 地圖導航、最短距離 |
| Bellman-Ford | 處理負權圖的最短路徑 | O(VE) | 有負邊權的圖 |
| Floyd-Warshall | 所有點對點的最短路徑 | O(V³) | 小圖、全距離查詢 |
| Prim / Kruskal | 最小生成樹 | O(E log V) | 網路連線、鋪電纜 |
| Topological Sort | 有向無環圖（DAG）排序 | O(V + E) | 任務排序（前置條件處理） |
| Union-Find | 判斷集合是否聯通、合併集合 | 幾乎 O(1) | 圖中連通區塊、社群判斷 |
🔢 七、數學與字串演算法
| 分類 | 演算法 | 用途 |
|---|---|---|
| 數學 | 最大公因數（GCD）/ 最小公倍數（LCM） | 比例、分數、數字問題 |
| 快速冪（Fast Exponentiation） | 大數次方、加密運算 | |
| 篩法（Sieve of Eratosthenes） | 找所有質數 | |
| 組合 / 排列 | 統計、遞迴 / DFS | |
| 字串處理 | KMP、Rabin-Karp、Boyer-Moore | 字串比對演算法（比原始比對快） |
| Trie | 前綴查詢、自動補字 | |
| Z-algorithm | 找子字串（類似 KMP） |
🧠 八、其他常見演算法技巧
| 技巧 | 概念 | 用途 / 範例 |
|---|---|---|
| Sliding Window | 移動範圍來降低重複運算 | 最長子陣列、固定長度計算平均、兩指標 |
| Two Pointers | 兩指標向中間移動，常配排序使用 | 合併排序陣列、找兩數和為 target |
| Binary Search（進階） | 不只查單點，也可查最小最大條件 | 最小可行值、搜尋答案空間 |
| Backtracking | 試錯、回朔法 | N 皇后、數獨、排列組合 |
| Bit Manipulation | 位元操作 | 權限控制、找單一重複元素 |
-
📋 面試時很常考：
- 排序 + 搜尋（尤其是 Binary Search）
- BFS / DFS
- Sliding Window / Two Pointers
- Dynamic Programming（DP）
- 貪婪法 + Backtracking
-
⚙️ 實務開發中常遇到：
- HashMap / Stack / Queue
- 排序 + Trie（字串輸入）
- Graph（導航、推薦系統）
- DP（優化成本、資源分配）