算法笔记：复杂度分析复盘

常见操作复杂度

容易记混的点

快速排序的平均复杂度是 $O(n \log n)$，但最坏情况会退化到 $O(n^2)$；归并排序稳定在 $O(n \log n)$，代价是需要 $O(n)$ 额外空间。

堆排序是 $O(n \log n)$ 且原地，但它不稳定，实际运行常数往往比快排大。

复杂度是增长趋势，不是运行时间。$n$ 很小的时候常数项说了算。

主定理

对于形如 $T(n) = aT(n/b) + O(n^d)$ 的递推：

$$T(n) = \begin{cases} O(n^d) & d > \log_b a \\ O(n^d \log n) & d = \log_b a \\ O(n^{\log_b a}) & d < \log_b a \end{cases}$$