聊聊提供了用渐近符号表示许多由分治法得到的递推关系式的Master Theorem

主定理 Master Theorem

对于采用分治策略的算法, 其递归方程一般可用主定理口算求解

内容

假设有递推关系式 $T(n) = aT(\dfrac{n}{b}) + \Theta(n), \space a \ge 1, b > 1$ 其中,

  • $n$ 为问题规模
  • $a$ 为递归子问题的数量
  • $\dfrac{n}{b}$ 为每个子问题的规模 假设每个子问题的规模基本一样
  • $f(n)$ 为递归以外进行的计算

则该算法的渐进时间复杂度 $\Omicron$ 可分为以下三种情形讨论

  • 情形1:

    如果 $\exists \space \epsilon > 0 \space (\epsilon 为一常数)$, 有 $f(n) = \Omicron (n^{\log_{b}{a} - \epsilon}) \space (多项式地小于)$

    则 $T(n) = \Theta (n^{\log_{b}{a}})$

  • 情形2:

    如果$\exists \space k \ge 0, \space (k为一常数)$, 有 $f(n) = \Theta (n^{\log_{b}{a}} \log^{k}n)$

    则 $T(n) = \Theta (n^{\log_{b}{a}} \log^{k + 1}n)$

  • 情形3:

    如果 $\exists \space \epsilon > 0 \space (\epsilon 为一常数)$, 有 $f(n) = \Omega(n^{\log_{b}{a} + \epsilon}) \space (多项式地大于)$

    同时 $\exists \space c < 1 \space (c为一常数)$ 以及充分大的 $n$ 满足 $af(\dfrac{n}{b}) \le cf(n)$

    则 $T(n) = \Theta (f(n))$

实际应用

在实际使用中我们并不需要记得那么复杂…

大概就记住下面一串?

$$
设递归方程为 \space T(n) = aT(\dfrac{n}{b}) + c(n^{d})
\space , 其中 \space a \ge 1 \space, b > 1
\

则所求问题的复杂度 \space

T(n) = \begin{cases}
\Theta (n^{d}\log{n}) \space , a = b ^ d
\
\
\Theta (n^d) \space , a < b ^ d
\
\
\Theta (n^{\log_{b}{a}}) \space , a > b ^ d
\end{cases}
$$

举例

每次问题规模减半, 则 $a = 1 \space , b = 2$

每次额外的计算为0, 则 $d = 0$

所以可得递推关系式 $T(n) = T(\dfrac{n}{2}) + c(1)$

上式满足 $a = b ^ d$ 即情形1

所以复杂度为 $\Theta (n^{0} \log{n}) = \Theta (\log{n})$

快速排序 Quick Sort

每次问题规模减半, 问题划分成两部分, 则 $a = 2, b = 2$

每次额外需要进行一次合并, 则 $d = 1$

所以可得递推关系式 $T(n) = 2T(\dfrac{n}{2}) + c(n^1)$

上式满足 $a = b^d$ 即情形1

所以复杂度为 $\Theta(n^1\log{n}) = \Theta(n\log{n})$

归并排序 Merge Sort

每次问题规模减半, 问题划分成两部分, 则 $a = 2, b = 2$

每次额外需要进行一次合并, 则 $d = 1$

所以可得递推关系式 $T(n) = 2T(\dfrac{n}{2}) + c(n^1)$

上式满足 $a = b^d$ 即情形1

所以复杂度为 $\Theta(n^1\log{n}) = \Theta(n\log{n})$

基数排序 Radix Sort

假设所取的基数为$base$则

每次问题规模变为$\dfrac{1}{base}$,但子问题规模变为 $base$ 倍, 则 $a = base \space, b = base$

每次需要分配一次桶为$\Omicron(n)$, 则$d = 1$

所以可得递推关系式 $T(n) = base * T(\dfrac{n}{base}) + c(n^1)$

上式满足 $a = b^d$ 即情形1

所以复杂度为 $\Theta(n^1\log{n}) = \Theta(n\log{n}) \simeq \Theta(w * n)$

Radix sort complexity is $\Omicron(wn)$ for n keys which are integers of word size w.

二叉树的遍历 Traversing Binary Tree

每次问题规模减半, 问题划分成两部分, 则 $a = 2, b = 2$

每次额外的计算为0, 则 $d = 0$

所以可得递推关系式 $T(n) = 2T(\dfrac{n}{2}) + c(1)$

上式满足$a > b^d$ 即情形3

所以复杂度为$\Theta(n^{\log_{2}2}) = \Theta(n)$