Siyuan

「算法笔记」Master 定理
「算法笔记」Master 定理
扫描右侧二维码阅读全文
10
2018/10

「算法笔记」Master 定理

在算法分析中,主定理提供了用渐近符号表示许多由分治法得到的递推关系式的方法。


关系式

假设有递归关系式 $T(n)=a\cdot T\left(\frac{n}{b}\right)+f(n)$,其中 $n$ 为问题规模,$a$ 为递推的子问题的数量,$\frac{n}{b}$ 为每个子问题的规模(假设基本一样),$f(n)$ 为额外需要进行的计算工作。

关系式中,$a\ge 1$,$b>1$,$f(n)$ 为函数,$T(n)$ 为非负整数。


主定理

记 $c_{\text{crit}}=\log_b a$,则有如下分类讨论:

  1. 如果存在常数 $c<c_{\text{crit}}$,满足 $f(n)=\mathcal O(n^c)$,那么 $T(n)=\Theta(n^{c_{\text{crit}}})$
  2. 如果存在常数 $k\ge 0$,满足 $f(n)=\Theta(n^{c_{\text{crit}}}\log^k n)$,那么 $T(n)=\Theta(n^{c_{\text{crit}}}\log^{k+1} n)$
  3. 如果存在常数 $c>c_{\text{crit}}$,满足 $f(n)=\Omega(n^c)$,那么 $T(n)=\Theta(f(n))$

注意

情形 $3$ 的条件:存在常数 $k<1$ 以及充分大的 $n$,满足 $a\cdot f\left(\frac{n}{b}\right)\le k\cdot f(n)$

发表评论