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

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

$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})$

其中a为递归中子递归个数, n/b为子递归的数据规模。

0%