递归方程

归并排序算法的递归方程

\begin{align} T(n) = \begin{cases} \Theta(1) & n=1 \\ 2T(\frac{n}{2})+\Theta(n) & n>1 \end{cases} \end{align}

这个方程的含义是如果只有 $1$ 个元素的数组需要做归并排序,那么在常数时间内就能得到有序数组。

如果是 $n$ 个元素的数组需要做归并排序,那么需要将问题一分为二,每个子问题各需要 $T(\frac{n}{2})$ 的时间。解决子问题以后,当前问题转化为合并有序数组问题,两个指针会不重复扫描每个元素一遍,复杂度为 $\Theta(n)$。

可以使用逐层展开法和变量替换法求解 $T(n)$,但是比较麻烦,仅作了解即可。

Master 定理

$$T(n) = aT(\frac{n}{b})+f(n), a \ge 1, b > 1, f(n) > 0$$

比较 $n ^ {\log_{b}{a}}$ 的阶和 $f(n)$ 的大小:

  • 若 $n ^ {\log_{b}{a}}$ 大,则 $T(n) = \Theta(n ^ {\log_{b}{a}})$
  • 若 $f(n)$ 大,则 $T(n) = \Theta(f(n))$
  • 若 $n ^ {\log_{b}{a}} = f(n)$,则 $T(n) = \Theta(n ^ {\log_{b}{a}} \log_{}{n}) = \Theta(f(n) \log_{}{n})$

对于归并排序,$a=2$,$b=2$,则 $n ^ {\log_{b}{a}} = n$。而 $f(n) = \Theta(n)$,它们的阶数相当。因此归并排序的时间复杂度 $T(n) = \Theta(n\log_{}{n})$。

Master 定理的证明

Previous