递归式求解-主方法

本文对递归式求解中很重要的主方法进行介绍总结。

主方法

主方法为如下形式的递归式提供了一种”菜谱式”的求解方法:
$$T(n) = aT(n/b) + f(n)$$
其中$a \ge 1, b \gt 1$是常数，$f(n)$是渐进正数。

上式描述了这样的一个算法运行时间: 他将原问题的规模为$n$的问题划分为$a$个小的子问题，每个子问题的规模为原来的$\frac{1}{b}$. $a$个子问题递归的进行求解，每个花费时间为$T(n/b)$。子问题合并的代价为$f(n)$

主定理

这里我将书上的定义直接贴上来了。

主方法依赖主定理:

令$a \ge 1$和$b \gt 1$是常数，$f(n)$是一个函数，$T(n)$是定义在非负整数上的递归式:
$$T(n) = aT(n/b) + f(n)$$
其中我们将忽略舍入问题$n/b$解释为$\lfloor n/b \rfloor$和$\lceil n/b \rceil$, 那么$T(n)$有如下渐进界:

若对某个常数$\epsilon > 0$有$f(n)=O(n^{\log_{b}a - \epsilon})$, $T(n) = \Theta(n^{\log_{b}a})$
若$f(n) = \Theta(n^{\log_{b}a})$, 则$T(n) = \Theta(n^{b}a lgn)$
若对某个常数$\epsilon > 0$有$f(n) = \Omega(n^{log_{b}a + \epsilon})$, 且对某个常数$c < 1$和所有足够大的$n$y有$af(n/b) \le cf(n)$, 则$T(n) = \Theta(f(n))$

主定理的直观理解

主定理其实主要是比较两个函数$f(n)$和$n^{\log_{b}a}$, 其中较大的那个决定最终递归式的渐近解。

若$n^{\log_{b}a} > f(n)$, 则就是情况1, 解就直接是$T(n) = \Theta(n^{\log_{b}a})$
若$n^{\log_{b}a} = f(n)$, 则就是情况2, 解就需要在$f(n)$的基础上乘上个对数因子$lgn$, $T(n) = \Theta(n^{\log_{b}a}lgn)$
若$n^{\log_{b}a} < f(n)$, 则就是情况3, 解为$T(n) = \Theta(f(n))$

主定理的细节理解

多项式意义上大于

主定理中，除了渐进大于(小于)以外，还有一个重要的概念就是多项式意义的大于(小于)(polynomially larger/smaller)

多项式大于意味着函数的比值会渐进的落在两个多项式之间。$f(n)$多项式意义上大于$g(n)$，当且仅当存在两个广义的多项式(分数指数也是可以的)$p(n), q(n)$使得如下不等式渐进成立:
$$p(n) \le \frac{f(n)}{g(n)} < q(n)$$

例如对于两个函数$n^2$和$\frac{n}{lgn}$, 我们有$\frac{n^2}{nlgn} = \frac{n}{lgn}$,
$$n^{\frac{1}{3}} \le \frac{n}{lgn} \le n$$
则函数$n^2$多项式意义上大于$nlgn$.

主定理中的细节

除了像上一部分那样有个大致的“大于”，“小于”的直观理解外，我们要理解定义中的具体细节，其实就是多项式大于/小于的应用。

第一种情况中，我们需要$f(n)$多项式意义上小于$n^{\log_{b}a}$，即$f(n)$渐进小于$n^{\log_{b}a - \epsilon}$。 $f(n)$必须渐近小于$n^{\log_{b}a}$, 同时要相差一个因子$n^{\epsilon}$, 其中$\epsilon$是大于0的常数。
第二种情况中，除了多项式意义上的大于以外，而且还要满足“正则”条件$af(n/b) \le cf(n)$

但是主方法中的三种情况并不能覆盖所有此形式的情况。情况1和情况2之间有一定的间隙，即$f(n)$渐近小于$n^{\log_{b}a}$d但不是多项式意义上的小于。同样的情况2和情况3也有类似的间隙。如果$f(n)$满足的条件正好落在间隙中，或者不满足情况3中的“正则”条件，就不能通过主方法来求解了。

例如求解如下递归式的时候:
$$T(n) = 2T(n/2) + nlgn$$

我们按照主方法，$a = 2, b = 2, f(n) = nlgn$

$$
n^{\log_{b}a} = n^{\log_{2}2} = n
$$

我们可以看到$f(n) = nlgn$ 渐近大于 $n^{\log_{b}a} = n$, 但是我们需要的是多项式意义上的大于即
$$
nlgn > n \cdot n^{\epsilon}, \epsilon > 0
$$
但是对于任意$\epsilon > 0$都无法满足$lgn$渐近大于$n^{\epsilon}$, 于是它并不是多项式意义上的大于，此递归式无法使用主方法来求解。

使用主方法的例子

对于矩阵乘法的Strassen方法递归式:
$$
T(n) = 7T(n/2) + \Theta(n^2)
$$

有$a = 7, b = 2, f(n) = \Theta(n^2)$, 因此$n^{\log_{b}a} = n^{\log_{2}7}$, 由于$2.8 < lg7 < 2.81$, 对于$\epsilon = 0.8$, 就有$f(n) = \Theta(n^2)$多项式意义上大于$O(n^{lg7})$, 于是我们便可以得到最终的解为:
$$
T(n) = \Theta(n^{lg7})
$$