老忘,记下来随时翻一翻。
$$ 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 为子递归的数据规模。