碼碼呼呼

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

發佈於 2018-09-11 評論 Algorithm 

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

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