已知 $$f(n)=af(n/b)+Cn^{d}$$
则
$$ f(n)\in\left{\begin{align} & O(n^{d}) & \log_{b}a < d \ & O(n^{d}\log n) & \log_{b}a = d \ & O(n^{\log_{b}a}) & \log_{b}a > d \end{align}\right. $$
理解记忆
- 组成部分
- $af(n/b)$ $\Rightarrow$ 分
- $n^{d}$ $\Rightarrow$ 治
- 原理
- $\log_{b}a$ $\Rightarrow$ 分の复杂度衡量
- $d$ $\Rightarrow$ 治の复杂度衡量
- 分治衡量不相等则为 $O(n^{大衡量})$，相等则 $O(n^{衡量}\log n)$