雅乐网

算法导论中的4.5节介绍了一个用于求解递归式的主定理，可以用来求解部分形如下面形式的递归式：

，其中a>=1 , b >1

描述的算法

把规模为n的问题分为a个子问题，每个子问题规模是n/b（原来的b分之一），分解子问题和合并子问题的时间是f(n)。

这样求解一个子问题需要时间T(n/b)，求解所有子问题需要时间aT(n/b)，再加上分解和合并的时间f(n)，就得到了总的时间T(n)。

主定理的三种情况

算法导论中介绍的三种情况是这样的：

这三个情况的表示可能会让有些人一头雾水，但是仔细研究后，可以直观的看出这三种情况是怎么分类的，而且使用起来并不麻烦。

其实这三种情况都是根据分解合并的函数 f(n) 和 的渐进大小关系来分的。注意是渐进意义上的大小，也就是多项式意义上的。所谓多项式意义，就是他们之间的差必须是n的几次方这种形式（比如n^2小于n^3，n^1.3 < n^1.4这种）。而如果相差logn这种形式就不是多项式意义上的，也不能应用主定理。

f(n) 和  中的较大者决定了T(n)的大小。

情况一：

 渐进大于 f(n) ，这时候T(n) = θ()

情况二：

f(n)和同阶，这时候T(n) = θ(   *  log n ) =  θ( f(n)  *  log n )

情况三：

f(n)多项式渐进大于,  T(n) =θ ( f(n) )

这时候还需要满足一个“正则条件”：存在c<1，af(n/b) < cf(n)。

主定理没有覆盖所有情况

如果情况一和三的渐进小于或大于不是多项式意义上的，而是logn之类的，就不能应用主定理。

还有，如果情况三不满足正则条件，也不能应用主定理。

例子

如果看了上面的三种情况还是摸不着头脑的话，没关系，看看下面的例子就好了。为了方便看a、b和f(n)，再把主定理的形式贴一边。

T(n) = 9T(n/3) + n

对比一下很容易得到 这个式子中： a = 9， b = 3, f(n) = n

那么我们来计算 ,等于 n^2

对比一下f(n)和，也就是n和n^2，显然n小于n^2，适用情况一。

得到解 T(n) = O () =θ(n^2)

T(n) = T(2n/3) + 1

a = 1, b = 3/2 , f(n) = 1

 = n^0 = 1 ,和1是同阶的，适应情况二。

T(n) = O( * logn) = θ(logn)

T(n) = 3T(n/4) + nlogn

a = 3, b = 4, f(n) = n*logn.

log(3,4)约等于0.793

 = n^0.793，虽然不准确，但是肯定小于n^1，和f(n)=nlogn进行比较，虽然f(n)包含logn的形式，但只看n的部分也至少要少了n^0.2 ，这个也是多项式意义上的，适用情况三。

使用情况三我们还需要验证正则条件

存在c<1，af(n/b) < cf(n)。把f(n)使用f(n) = nlogn代替

3* n/4 log(n/4) < c n logn

要想这个不等式成立，分别观察3/4n 和log(n/4)和右边对应的地方，显然右边的logn是大于左边的log(n/4)的，只要右边的cn 大于左边的3/4n 就可以了。

只要c大于3/4就可以，并且c<1 这样的c是存在的，至此可以应用情况3了

T(n) = θ (nlogn)

T(n)=2T(n/2)+nlogn

a = 2, b = 2, f(n) = nlogn

 = n 。我们注意到n确实是小于nlogn的，但是这并不是多项式意义上的小于，因为两个式子n的次数都是1，因此不能应用主定理。

这个递归式可以使用递归树进行求解。