# 时间复杂度必知

## 排序

| 算法           | Time                                   | Memory                                  | 特征                                                                                      |
| ------------ | -------------------------------------- | --------------------------------------- | --------------------------------------------------------------------------------------- |
| HeapSort     | O(NlogN)                               | O(1)                                    | **Not Stable**                                                                          |
| MergeSort    | O(NlogN)                               | <p>O(N)</p><p>reducible w/ in-place</p> | **Stable**                                                                              |
| QuickSort    | <p>O(NlogN)</p><p>O(N²) worst case</p> | <p>O(logN)</p><p>recursion stack</p>    | <p><strong>Not stable</strong></p><p><strong>Applied for O(N) finding RANK</strong></p> |
| CountingSort | O(N)                                   | -                                       | Assumes known range                                                                     |
| BucketSort   | O(N)                                   | -                                       | Assumes \~Unif(range)                                                                   |

## 搜索

| 算法           | <p>树</p><p>b=branch factor</p><p>m=tree depth</p> | <p>图</p><p>V=no. of vertices</p><p>E=no. of edges</p> |
| ------------ | ------------------------------------------------- | ----------------------------------------------------- |
| DFS          | O(bᵐ)                                             | O(V+E)                                                |
| BFS          | O(bᵈ), d=depth of solution                        | O(V+E)                                                |
| Toposort     | -                                                 | O(V+E)                                                |
| Dijkstra     | -                                                 | O((ElogV)                                             |
| Bellman-Ford | -                                                 | O(V\*E)                                               |
| MST          |                                                   | O(ElogV)                                              |