递推时间复杂度计算——master定理
我们将一个规模为 n 的问题，通过分治得到 a 个规模为$ \frac{n}{b} $的子问题，每次递归带来的额外计算为 f(n) ，那么我们得到以下关系式：
$T(n)=aT(\frac{n}{b})+f(n)$,
此外，我们定义一个$c_{crit}=log_{b}{a}$ ,它是这么计算的：
1. 当$f(n)=O(n^c)且c<c_{crit}$:
$T(n)=\Theta(n^{c_{crit}})$
2. 当$f(n)=O(n^c)且c=c_{crit}$:
$T(n)=\Theta(n^{c_{crit}}log{n})$
3. 当$f(n)>O(n^c)且c=c_{crit}$:
$T(n)=\Theta(f(n))$
参考链接：
版权声明：本文为tldr原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。