递归时间复杂度分析方法：Master 定理

编写算法时，可能因为对自己代码的复杂度的不清晰而导致错失良机，对于普通的递推或者说循环的代码，仅用简单的调和级数或者等差数列和等比数列即可分析，但是对于递归的代码，简单的递归树法并不方便，理解并记下Master定理，可以让事情变得轻松。

写此文以作笔记，如有错误，请联系博主。

Master 定理基本形式

对于一个递归式 $T(n)=aT(\frac{n}{b})+f(n)$，其中：

• $a\ge 1$ 和 $b>1$ 是常数；
• $f(n)$ 是一个给定的函数，
  Master 定理帮助我们确定 $T(n)$ 的渐进界。

有三种情况：

1. 如果 $f(n)=O(n^c)$，其中 $c<{\log }_{b}a$， 那么 $T(n)=\Theta (n^{{\log }_{b}a})$。
2. 如果 $f(n)=\Theta (n^c)$，其中 $c={\log }_{b}a$， 那么 $T(n)=\Theta (n^c\log n)$。
3. 如果 $f(n)=\Omega (n^c)$，其中 $c>{\log }_{b}a$，且满足一定的平滑条件（即 $af(n/b)\le kf(n)$ 对于某个常数 $k<1$ 和充分大的 $n$）， 那么 $T(n)=\Theta (f(n))$。

特定的例子

考虑 $T(n)=2T(\frac{n}{2})+O(n\log n)$，这里 $a=2$, $b=2$, 和 $f(n)=n\log n$。显然，$f(n)$ 不符合 Master 定理的标准形式中的 $f(n)=O(n^c)$，因为增长速度比任何 $n^c$ 形式要快。因此，直接应用标准 Master 定理的三种情况并无法获得解答。

在这种特殊情况下，$T(n)=2T(\frac{n}{2})+n\log n$ 的时间复杂度实际上是 $O(n(\log n{)}^2)$。如有兴趣请自行查找证明过程。