主定理

《目录》

使用主定理求解递归式

? 算例 ?

证明主定理

使用主定理求解递归式

主定理是分治算法分析中非常重要的定理。

如，我们要处理一个规模为的问题通过分治，得到个规模为 $\frac{n}{b}$ 的问题，分解子问题和合并子问题的时间是 f(n) ：

$T(n) = aT(\frac{n}{b})+f(n)$

在上面这个式子里，我们得要求主定理 b=1 时，递推无意义)， f(n) 是渐进意义上的正数。

回顾一下，和的含义：

个子问题，即是原问题分为子问题的个数；
每个子问题的规模是 $\frac{n}{b}$ ；
分治算法共三部分，分治合，而就是分+合的时间。

$\left \lfloor \frac{n}{b} \right \rfloor$ 和 $\left \lceil \frac{n}{b} \right \rceil$ ，向下取整和向上取整的细节，并不会影响主定理的推导，具体的数学证明，略。

如果对分治算法不熟悉，建议先看《递推式分析》。

而后呢，根据上面的式子我们会得到三种情况：

若有实数大于零( $f(n)=O(n^{log_{b}a-\varepsilon })$ ，则 $T(n)=\Theta (n^{log_{b}a})$ ；
若 $f(n)=\Theta (n^{log_{b}a})$ ，则 $T(n)=\Theta (n^{log_{b}a}~logn)$ ；
若有实数大于零( $f(n)=\Omega (n^{log_{b}a+\varepsilon })$ ，且有一个实数小于一()，使得较大的，满足 $af(\frac{n}{b})\leqslant cf(n)$ ，这时候则 $T(n) = \Theta (f(n))$ 。

这三种情况看起来很复杂，搞清楚他们之间的关系，快速记忆就简单了。

对于三种情况的每一种，我们将函数 f(n) 与 $n^{log_{b}a}$ 比较，俩个函数较大者将决定递归式的解。

若函数 $n^{log_{b}a}$ 更大，如情况1，则解是 $T(n)=\Theta (n^{log_{b}a})$ ；注意小于 $n^{log_{b}a}$ 是渐进意义上的，要差一个因子量级更大，如情况3，则解是 $T(n) = \Theta (f(n))$ ；注意大于 $n^{log_{b}a}$ 是渐进意义上的，要差一个因子量级 $af(\frac{n}{b})\leqslant cf(n)$ ；
若俩个函数相等，如情况2，则乘上一个对数因子，解为 $T(n)=\Theta (n^{log_{b}a}~logn)$ ；
上面的三种情况并未覆盖的所有可能性，情况1、情况2 之间存在间隙，可能小于 $n^{log_{b}a}$ 但不是多项式意义上的小于；情况2、情况3 之间也存在间隙，可能大于 $n^{log_{b}a}$ 但不是多项式意义上的大于；若函数在这俩个间隙中，或者是情况3 中要求的 $af(\frac{n}{b})\leqslant cf(n)$ 条件不成立，就不能使用主方法来解决递归式。

首先，得明白一个基准函数： $\Theta (n^{log_{b}a})$ 。

有了基础函数之后，就可以根据 TA 来判定情形之间的关系。

那我们该如何记忆这个基准函数呢？？

原来的函数是： $aT(\frac{n}{b})+f(n)$ ，为底数，如果化为对数形式也是以为底( $log_{b}~a$ )；

原函数是一个多项式，和都是常数，算出来肯定也是一个具体的数值。

所以，我们要记这样一个基准多项式(基准函数)： $\Theta (n^{?})$ ，次方(即 )是取对数的。

接下来，是以上三种情况的判定：

是弱于基准的(渐进意义上)， $O(n^{log_{b}a-\varepsilon })<\Theta (n^{log_{b}a})$ ；
是等于基准的(渐进意义上)， $\Theta (n^{log_{b}a})=\Theta (n^{log_{b}a})$ ；
是强于基准的(渐进意义上)，? 算例 ?
算例1： $T(n)=4T(\frac{n}{4})+\Theta (1)$ (乐高铺积木)

分析，，基准函数是 $\Theta (n^{log_{4}4})$ ，因为 $log_{4}4=1$ ，所以基准函数是 $\Theta (n)$ 。

那  又是什么呢？？？

$f(n) = \Theta (1)$ ，比基准函数 $\Theta (n)$ 要弱，我们取一个实数( $\varepsilon=1$ ) ，即 $\Theta (1)=O(n^{1-\frac{1}{2}}) = O(\sqrt{n})$ 。

得到 $T(n)=\Theta (n )$ .

算例2： $T(n)=T(\frac{n}{2})+\Theta (1)$ (二分查找)

分析，，基准函数是 $\Theta (n^{log_{2}1})$ ，因为 $log_{2}1=0$ ，所以基准函数是 $\Theta (1)$ 。

那  又是什么呢？？？

$f(n) = \Theta (1)$ ，基准函数也是 $\Theta (1)$ ， = 基准函数，再乘上一个，即 $T(n)=\Theta (logn)$ 。

算例3： $T(n)=2T(\frac{n}{2})+\Theta (n)$ (归并排序)

分析，，基准函数是 $\Theta (n^{log_{2}2})$ ，因为 $log_{2}2=1$ ，所以基准函数是 $\Theta (n)$ 。

那  又是什么呢？？？

$f(n)=\Theta (n)$ ，基准函数也是 $\Theta (n)$ ， = 基准函数，最后 $T(n)=\Theta (n~logn)$ 。

算例4： $T(n)=7T(\frac{n}{2})+\Theta (n^{2})$ (Strassen 算法)

分析，，基准函数是 $\Theta (n^{log_{2}7})$ ，大概是 $n^{2.8}$ 。

那  又是什么呢？？？

$f(n)=\Theta (n^{2})$ ，基准函数是 $\Theta (n^{log_{2}7}) = \Theta (n^{2.8})$ 在这基础上减去 0.1 即俩者相等 $f(n)=\Theta (n^{2.8-0.1})$ ，最后 $T(n)=\Theta (n^{log_{2}7})$ 。

算例5： $T(n)=3T(\frac{n}{4})+n~logn$   (摘自《算法导论》)

分析，，基准函数是 $\Theta (n^{log_{4}3})$ ，大概是 $n^{0.8}$ 。

那  又是什么呢？？？

  ，比 $n^{0.8}$ 要强， $\varepsilon =0.1$ (取 0.1 依然比 $n^{0.8}$ 大)， $f(n)=\Omega (n^{0.8+0.1})$ 。

强的话，再看看是否满足 $af(\frac{n}{b})\leqslant cf(n)$ 。

把  代入： $3(\frac{n}{4})log\frac{n}{4}\leqslant \frac{3}{4}nlogn$ 。

得到， $c = \frac{3}{4},c<1$ ，满足条件，因此 $T(n)=\Theta (f(n))=\Theta (n~logn)$ 。



证明主定理

已经知道了基准(函数)怎么使用，可我们还不知道为什么会得到若干个渐进记号，我们会使用递归树来证明。

假设 $n=b^{L}$ ，每一次除以，除  次会为 1。

举个例子， $T(n)\left\{\begin{matrix} \Theta (1) &n=1 \\ aT(\frac{n}{b})+f(n) & n=b^{i},(i\geqslant 1) \end{matrix}\right.$

我们想知道的是， $T(n)=\Theta (n^{log_{b}a})+\sum_{j=0}^{L-1}a^{j}f(\frac{n}{b^{j}}), L = log_{b}n$ 。

从上面的式子看出：
- $\Theta (n^{log_{b}a})$ 即基准函数；
- $\sum_{j=0}^{L-1}a^{j}f(\frac{n}{b^{j}})$ 注重的是基准函数和的强弱关系；
- $L = log_{b}n$ 是递归树的高度。
在递归树上证明时，我们写的简单些，直接把结点 f(m) 调用开销画上去。
- 第一层的代价是：；
- 第二层的代价是： $af(\frac{n}{b})$ ；
- 第三层的代价是： $a^{2}f(\frac{n}{b^{2}})$ ；
- $\vdots$ $\vdots$ $\vdots$ $\vdots$
- 负一层的代价是： $\Theta (n^{log_{b}a})$ 。
整个递归树高度是，总的代价是： $\Theta (n^{log_{b}a})+\sum_{j=0}^{L-1}a^{j}f(\frac{n}{b^{j}})$ 。

这些项会造成什么影响？

对于的影响，我们要分析三种情况：

总个的表达式： $g(n)=\sum_{j=0}^{L-1}a^{j}f(\frac{n}{b^{i}})$
- 第一种情况： $f(n)=O(n^{log_{b}a-\varepsilon })$ ，，我们求的就是这个项： $\sum_{j=0}^{L-1}a^{j}(\frac{n}{b^{j}})^{log_{b}a-\varepsilon }$ 。
思考一下，我们能不能这个式子化为等比数列？

无关的项： $n^{log_{b}a-\varepsilon }$ 提出来，里面是 $\sum_{j=0}^{L-1}a^{j}(\frac{n}{b^{j}})^{log_{b}a-\varepsilon }$ 。

$\frac{a^{j}b^{j\varepsilon }}{b^{jlog_{b}a}}$ ， $b^{j\varepsilon }=(b^{\varepsilon })^{j}$ ， $(b^{log_{b}a})^{j}=a^{j}$ 。

$\cdots$

得出， $g(n)=O(n^{log_{b}a})$ 。
- 第二种情况： $f(n)=\Theta (n^{log_{b}a})$ ，，我们求的就是这个项： $\sum_{j=0}^{L-1}a^{j}(\frac{n}{b^{j}})^{log_{b}a}$ 。
把 $n^{log_{b}a}$ 提出来，里面是 $\sum_{j=0}^{L-1}a^{j}\frac{1}{b^{j log_{b}a}}$ 。

$(b^{log_{b}a})^{j}=a^{j}$ ，消掉后 $\sum_{j=0}^{L-1}a^{j}\frac{1}{b^{j log_{b}a}}$ 这个求和就是对一求和，那是多少个一呢？

一共 $n^{log_{b}a}*L$ 个一，这个结果也等同于 $n^{log_{b}a}*L=n^{log_{b}a}*log_{b}n$ 。
- 第三种情况： $f(n)=\Omega (n^{log_{b}a+\varepsilon })$ ， $af(\frac{n}{b})\leqslant cf(n)$ 。
  
     $a^{j}f(\frac{n}{b^{j}})-a^{i-1}(af(\frac{n}{b^{i}}))\leqslant a^{j-1}*cf(\frac{n}{b^{i-1}})$
  
  $\leqslant a^{j-2} * c^{2}f(\frac{n}{b^{j-2}})$
  
     $\vdots$ $\vdots$    $\vdots$
  
     $\leqslant c^{j}f(n)$
  
  形成一个 $c^{j}$ 的等比数列，而  在里头保持不变，可以挪出来。
  
  而这些等比数列最终加起来也不会超过 $\frac{1}{1-c}$ ，因此 $f(n)*\frac{1}{1-c}$ 乘的，也是一个常数项，总时间是 $\Theta (f(n))$ 。
  
  
  
  
  
  版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们举报，一经查实，本站将立刻删除。
  发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/202226.html原文链接：https://javaforall.net

使用主定理求解递归式

证明主定理

关于作者

全栈程序员-站长

发表回复

主定理

使用主定理求解递归式

证明主定理

关于作者

全栈程序员-站长

相关推荐

如何配置交换机端口镜像

if过多如何重构_多个else if用法

ssh配置config文件命令_config文件能删除吗

sqlserver不存在或拒绝访问怎么办_sql数据库连接不上

完整教程：Jenkins 可观测最佳实践

gatk过滤_GATK–使用转载

发表回复