Try harder.

递归时间复杂度计算:master 公式

2018.09.11

老忘,记下来随时翻一翻。

$$ 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 为子递归的数据规模。