主方法求解递归式
在分析递归的算法时，主方法可以较快的计算出算法的时间复杂度
主方法可以用于满足以下形式的递归式。
其中$a\geq1和b>1$是常数，$f(n)$是渐进函数。
主方法描述的算法：将原本规模为$n$的问题，分解为 $a$ 个规模为 $n/b$ 的子问题，其中 $a,b\in \mathbb{Z^+}$，函数 $f(n)$ 包含了问题分解和子问题合并的代价。
下面是归并排序的递归式:
其中，$a=2, b=2, f(n)=\Theta(n^2)。$
在具体处理过程中,会遇到 $n/b$ 可能不是整数的情况。可以将 $a$ 项 $T(n/b)$全都替换为$T(\lfloor n/b \rfloor)或T(\lceil n/b\rceil)$ 并不会影响递归式的渐进性质。
主定理
主定理：$a\geq1和b>1$是常数，$f(n)$是一个函数，$T(n)$是定义在非负整数上的递归式:
其中将 $n/b$ 解释为$\lfloor n/b \rfloor或\lceil n/b\rceil$。那么$T(n)$有如下渐近界：
1.若对某个常数 $\epsilon >0$有 $f(n)= O(n^{log_ba-\epsilon})$ ,则 $T(n)=\Theta(n^{log_ba})。$
2.若$f(n)=\Theta(n^{log_ba})$，则 $T(n)=\Theta(n^{log_ba} lgn)$
3.若对某个常数$\epsilon>0$ 有 $f(n)=\Omega(n^{log_ba+\epsilon})$，且对某个常数 $c<1$ 和所有足够大的 $n$ 有 $af(n/b)\leq cf(n)$，则 $T(n)=\Theta(f(n))$。
实际上就是将函数 $f(n)$ 和函数 $n^{log_ba}$ 进行比较。如情况1和情况3，两者的较大者决定了递归式的解。对于情况2，则再乘上一个对数因子 $lgn$ ，解为 $T(n)=\Theta(n^{loa_ba} lgn)=\Theta(f(n) lgn)$。
注意: 对于第1种情况和第3种情况的 $\mathbf{f(n)}$ 渐进小于和渐进大于 $\mathbf{n^{log_ba}}$，其中相差一个因子 $n^\epsilon$，其中 $\epsilon$为大于0的常数，即要满足 多项式的差距。同时第三种情况还要满足 “正则”条件 $af(n/b)\leq cf(n)$。
这三种情况未覆盖 $f(n)$ 的所有可能性。 即 $f(n)$ 不满足多项式级别的渐进小于 $n^{log_ba}$而处于情况1和情况2之间。同理，不满足 $f(n)$ 渐进大于而处于 $n^{log_ba}$ 而处于情况2和情况2之间，或则情况3而不满足正则条件，均不能使用主方法求解递归式。
主方法使用例子
1、
其中 $a=9,b=3,f(n)=n$。很容易求解 $n^{log_ba}=n^2=\Theta(n^2)$。
有$f(n)=n= O( n^{log_ba-\epsilon})$，其中$\epsilon=1$，故满足情况1，因此得出$T(n)=\Theta(n^2)$。
2、
其中 $a=1,b=3/2,f(n)=1$。$n^{log_ba}=n^{log_{3/2}1}=\Theta(1)$。
有$f(n)=\Theta(n^{log_ba})=\Theta(1)$。因此满足情况2，则 $T(n)=\Theta(n^{log_ba} lgn)=\Theta(lgn)$。
3、
其中 $a=3,b=4,f(n)=nlgn$。$n^{log_ba}=n^{log_43}= O(n^{0.793})$。由于$f(n)=\Omega(n^{log_43+\epsilon})$，其中$\epsilon\approx0.2$。
接下来证明正则条件，即
显然，当$c=3/4$时，不等式成立。
故$T(n)=\Theta(f(n))=\Theta(nlgn)$
下面这个递归式不能运用主方法
4、
其中 $a=2,b=2,f(n)=nlgn$，$n^{log_ba}=\Theta(n)$，
可能会得到错误的结论有：$f(n)=\Omega(n^{log_22+\epsilon})$。然后继续求解下去。
实际上，不满足之前提到的情况1和情况3的渐进差距需要时多项式级别的。
即：
这里的 $\mathbf{\omicron}$ 符号代表非渐进紧确的上界，
如：$f(n)=\omicron(g(n))$: $\forall c>0$，$\exists$常量$n_0>0$，使得 $\forall n\geq n_0$，有 $0 \leq f(n) \leq cg(n)$。简单理解小于但不等于。
即不满足多项式级别的大于。故处于情况2和情况3之间。不可以采用主方法求解。
练习题4.5-1： 建议自己动手做完后对照。
a.
其中$a=2,b=4,f(n)=1$, $n^{log_ba}= \sqrt n$。
有 $f(n) = O(n^{log_ba-\epsilon}) = O(n^{0.5-\epsilon})$，其中$\epsilon = 0.5$。
故 $T(n) = \Theta(n^{log_42}) = \Theta(\sqrt n)$
b.
同上,可以求出 $n^{log_ba}$，由于 $f(n) = \sqrt n =\Theta(\sqrt n) = \Theta(n^{log_42})$
故$T(n) = \Theta( f(n)lgn) = \Theta(\sqrt n lgn)$
c.
同上，求出 $n^{log_ba}$，由于 $f(n) = \Omega(n^{0.5 + \epsilon})$, 其中 $\epsilon =0.5$。接下来证明正则条件：
显然，取 $c = \frac 1 2$时，满足条件。故 $T(n) = \Theta(f(n)) = \Theta(n)$
d.
同上，求出 $n^{log_ba}$，由于 $f(n) = n^2 = \Omega(n^{logb_a+\epsilon})$，其中 $\epsilon = 1.5$。下面证明正则条件：
显然，取 $c = 1/8$ 时，满足条件。故 $T(n) = \Theta( f(n) ) = \Theta(n^2)$。
参考文献：算法导论