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

发表于 | 分类于 | 评论数： | 阅读次数：
本文字数： 308 字 | 阅读时长 ≈ 1 分钟

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

$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%