Cheat Sheet
演算法複雜度速查表。
Big-O Complexity Chart
Common Data Structure Operations
Sorting Algorithms
- In-place sorting : 代表只需要使用
O(1)額外空間對序列進行排序 - Stable sorting : 代表相同數值的元素在經過排序後，相對順序不會改變，這對於多索引排序很重要
| Algorithm | Stable? | In-place? |
|---|---|---|
| Bubble Sort | Yes | Yes |
| Insertion Sort | Yes | Yes |
| Selection Sort | No | Yes |
| Merge Sort | Yes | No |
| Quick Sort | No | Yes |
| Heap Sort | No | Yes |
| Counting Sort | Yes | No |
| Radix Sort | Yes | No |
| Bucket Sort | Yes | No |
| Shell Sort | No | Yes |
| Tim Sort | Yes | No |
| Tree Sort | Yes | No |
Searching Algorithms
| 算法名稱 | 時間複雜度 | 空間複雜度 |
|---|---|---|
| 線性搜索 (Linear Search) | O(n) | O(1) |
| 二分搜索 (Binary Search) | O(log n) | O(1) |
| 跳躍搜索 (Jump Search) | O(√n) | O(1) |
| 插值搜索 (Interpolation Search) | 平均: O(log log n), 最壞: O(n) | O(1) |
| 指數搜索 (Exponential Search) | O(log n) | O(1) |
| 深度優先搜索 (DFS) | O(V + E) | O(V) |
| 廣度優先搜索 (BFS) | O(V + E) | O(V) |
| 貪心最佳優先搜索 (Greedy BFS) | O(b^m) | O(b^m) |
| Dijkstra 算法 | O((V + E) log V) | O(V) |
| A* 搜索 (A* Search) | O(b^d) | O(b^d) |
| 蒙特卡洛樹搜索 (MCTS) | 取決於模擬次數和樹深度 | O(b^d) |
| 模擬退火 (Simulated Annealing) | 取決於冷卻調度和迭代次數 | O(1) |
| 遺傳算法 (Genetic Algorithm) | 取決於種群大小和代數 | O(population size) |
| KMP 算法 (Knuth-Morris-Pratt) | O(n + m) | O(m) |
| Rabin-Karp 算法 | 平均: O(n + m), 最壞: O(nm) | O(1) |
| Boyer-Moore 算法 | 最佳: O(n/m), 最壞: O(nm) | O(k) |
| 模糊搜索 (Fuzzy Search) | 通常 O(n*m) | 取決於具體算法 |
| 哈希搜索 (Hash Search) | 平均: O(1), 最壞: O(n) | O(n) |
| 布隆過濾器 (Bloom Filter) | O(k) 插入和查詢 | O(m) |