老忘,记下来随时翻一翻。
$T(n) = aT(\frac{n}{b}) + O(n^d)$
其中: $\log_{b}a > d \quad \Rightarrow \quad O(n^{\log_{b}a})$
$\log_{b}a < d \quad \Rightarrow \quad O(n^{d})$
$\log_{b}a = d \quad \Rightarrow \quad O(n^{d}*\log{n})$
$\log_{b}a > d \quad \Rightarrow \quad O(n^{\log_{b}a})$
$\log_{b}a < d \quad \Rightarrow \quad O(n^{d})$
$\log_{b}a = d \quad \Rightarrow \quad O(n^{d}*\log{n})$
其中a为递归中子递归个数, n/b为子递归的数据规模。