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) |
| Dijkstra 算法 | O((V + E) log V) | O(V) |
| A* 探索 (A* Search) | O(b^d) | O(b^d) |