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

上海建设咨询有限公司下载优化大师安装桌面

news 2025/7/22 14:14:48

上海建设咨询有限公司,下载优化大师安装桌面,大连建设主管部门官方网站,广告视频素材网站主定理（Master Theorem）是用于分析递归算法时间复杂度的一个重要工具。它适用于形式化定义的一类递归关系，通常采用分治策略解决问题的情况。目录主定理简化版的局限主定理一般形式情况1： n l o g b a n^{log_{b}{a}} nlogba …

主定理（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}$

子问题数量小于1

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

分解问题和合并解的时间不是 $n^{c}$

$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)$ 的增长率关系

情况1： $n^{log_{b}{a}}$ 比 $f (n)$ 增长的快

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

$n^{log_{b}{a}}=n^{2}$ ,
$f(n)=n=O(n^{2-\epsilon }),\epsilon \le1$
$\Rightarrow T(n)=O(n^{2})$

情况2： $n^{log_{b}{a}}$ 与 $f (n)$ 增长率类似

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

$n^{log_{b}{a}}=n^{log_{3/2}1}=n^{0}=1$ ,
$f(n)=1=Θ(n^{log_{b}{a}}log^{0}n)$
$\Rightarrow T(n)=O(log n)$

情况3： $n^{log_{b}{a}}$ 比 $f (n)$ 增长的慢

$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)$