当前位置：首页 > article >正文

主定理（一般式）

article 2024/11/14 13:57:38

主定理（Master Theorem）是用于分析递归算法时间复杂度的一个重要工具。它适用于形式化定义的一类递归关系，通常采用分治策略解决问题的情况。

主定理简化版的局限

主定理简化版的三种情况：

$I F$ $f(n) = O(n^ {log_b(a - ε)})$ ，and $ε > 0$ ，Then $T(n) = Θ(n^{log_b(a)})$
$I F$ $f(n) = Θ(n^{log_b(a)} ·log^k n)$ ，and $k \geq 0$ ，Then $T(n) = Θ(n^{log_b(a)} · log^{k+1} n)$
$I F$ $f(n) = Ω(n^{log_b(a + ε)})$ ，and $ε > 0$ ， $f(\frac{n}{b}) ≤ c · f(n)$ 对于某个常数 $c < 1$ 和所有足够大的 $n$ 成立，Then $T (n) = Θ (f (n))$

简化形式具有一定的限制条件，比如形式上必须是： $T(n)=a·T(\frac{n}{b})+f(n)$

并且 $f(n) = n^{c}$

三个反例：

$\cdot T(\frac{n}{2})+n^{2}$

$T(n)=\frac{1}{2}T(\frac{n}{2})+n^{2}$

$T(n)=2T(\frac{n}{2})+nlogn$

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

$I F$ $\exists ε > 0$ 使得 $f(n) = O(n^ {log_b(a - ε)})$ ，Then $T(n) = Θ(n^{log_b(a)})$
$I F$ $\exists k ≥ 0$ 使得 $f(n) = Θ(n^{log_b(a)} ·log^k n)$ ，Then $T(n) = Θ(n^{log_b(a)} · log^{k+1} n)$
$I F$ $\exists ε > 0$ 使得 $f(n) = Ω(n^{log_b(a + ε)})$ ，
且对于某个常数 $c < 1$ 和所有足够大的 $n$ 有 $f(\frac{n}{b}) ≤ c · f(n)$ ，Then $T (n) = Θ (f (n))$

主要考虑函数 $n^{log_{b}{a}}$ 与 $f (n)$ 的增长率关系

$T(n)=9T(\frac{n}{3})+n$

$T(n)=T(\frac{2n}{3})+1$

$f (n)$ 比 $n^{log_{b}{a}}$ 增长的更快，至少要快 $Θ(n^{\epsilon})$ 倍，且 $af(\frac{n}{b}) \le cf(n)$

$T(n)=3T(\frac{n}{4})+nlogn$

$n^{log_{b}{a}}=n^{log_{4}3=n^{0.793}}$ ,
$f(n)=nlogn=Ω(n^{log_{4}3+\epsilon }),\epsilon \le0.207$
$af(\frac{n}{b})=3(\frac{n}{4})log(\frac{n}{4}) \le \frac{3}{4}nlogn=cf(n),c=\frac{3}{4}$
$\Rightarrow T(n)=O(nlogn)$