主定理

《目录》

使用主定理求解递归式
? 算例 ?
证明主定理

使用主定理求解递归式

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

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

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

在上面这个式子里，我们得要求 $a \geqslant 1, b> 1$ (如果 $b=1$ 时，递推无意义)， $f(n)$ 是渐进意义上的正数。

回顾一下， $a$ 和 $b$ 的含义：

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

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

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

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

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

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

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

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

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

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

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

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

$f(n)$ 是弱于基准的(渐进意义上)， $O(n^{log_{b}a-\varepsilon })<\Theta (n^{log_{b}a})$ ；
$f(n)$ 是等于基准的(渐进意义上)， $\Theta (n^{log_{b}a})=\Theta (n^{log_{b}a})$ ；
$f(n)$ 是强于基准的(渐进意义上)， $\Omega (n^{log_{b}a+\varepsilon })>\Theta (n^{log_{b}a})$ 。

? 算例 ?

算例1： $T(n)=4T(\frac{n}{4})+\Theta (1)$ (乐高铺积木)

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

那 $f(n)$ 又是什么呢？？？

$f(n) = \Theta (1)$ ， $f(n)$ 比基准函数 $\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)$ (二分查找)

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

那 $f(n)$ 又是什么呢？？？

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

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

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

那 $f(n)$ 又是什么呢？？？

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

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

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

那 $f(n)$ 又是什么呢？？？

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