递归式求解的三种方法

本节阐述递归式求解的三种方法：递归树、代入法和主定理法。

O、写在前面

在分治法中，时间复杂度T(n)往往具有递归性质，被递归式所表示，譬如T(n)=T(n/4)+T(3n/4)+n，其含义其实是在表示，一个规模为n的问题，被分解为两个规模分别为n/4和3n/4的子问题（其和刚好为n）。容易知道的是T(n)中必然包含子问题的复杂度T(n/4)和T(3n/4)，除此之外，还需要加上问题合并和分解的代价，我们设为f(n)，在本例f(n)=n。

本节涉及的三个算法之间，也有着密切的联系。

递归树法，顾名思义，根据递归式的问题分解可以建立递归树。本方法是通过图像化分析，直接得出问题时间复杂度T(n)，直观，但是缺乏严谨性。因此，该方法往往是用来猜测T(n)解析式，以让代入法证明之。

代入法，事先猜测时间复杂度的表达式，然后利用渐进上界等定义证明。猜的过程一方面靠经验，另一方面可通过递归树法分析，也有可能极其难猜（譬如T(n)=nlog^2(n)。不过其关键还是在于证明，证明方法错了，还是大写的一个G......

主定理法，特殊解法，与递归式的形式直接相关。一般而言是解形如T(n)=aT(n/b)+f(n)的递归式，通过不同的条件可直接给出时间复杂度的渐进界。

一、递归树法

本方法仅通过一个例子介绍

[图片上传失败...(image-a7a5d2-1663928156825)]

从原递归式容易知道，每一层分解、合并各个子问题的代价总和均为n。根据分治的思想，如果没有到叶子结点，那么每一层是不会存在“解决问题”的时间复杂度的。上例比较特殊，分解子问题并非等分，因此会导致递归树各分支到达叶子结点的深度是不同的，且越靠左到达叶子结点越早。

对于最左分支，问题规模以1/4的速度下降，是最早到达叶子结点——问题规模为O(1)——的分支。假设在某一层，最左分支刚好到达叶子结点，可以浅浅分类讨论一下：

• 对于该层以前的层，没有解决问题的代价，只有分解合并的代价，为n

• 对于该层而言，最左分支到达叶子结点，没有分解合并的代价，但是需要加上解决问题的代价。因为到达了叶子结点，所以解决问题的代价为O(1)，而由于分解合并代价为O(n)(n=1)，可以认为该层总复杂度仍为n

• 对于该层之后的层而言，缺少一个分支，因此不管怎样，其总复杂度都小于n

总共来说，子问题分解彻底时，每一层问题的分解和合并时间复杂度为O(n)（渐进上界），这个结论包含最低层。而结合深度可知，总时间复杂度为O(nlog_{4/3}n)根据换底公式可换算为标准形式

到此，递归树可以说做到了仁至义尽，但是不得不承认，本题的答案是\Theta(nlog(n))，即nlog(n)是一个渐进紧确界，而非仅仅渐进上界，由此可见递归树法的缺漏，进一步证明将放在代入法。

本例较为特殊，子问题的分解并不是等分的。通过该问题可以更为透彻的理解整个分析过程，但仍需要说一下等分的情况：

则每一层分解合并代价为f(n)，分解为a个规模为原来的1/b的子问题，解决问题全部放到了叶子结点层（不会出现上例那种叶子结点所在层数可能不在最底层），由于叶子结点解决问题复杂度为O(1)，因此只需要计算叶子节点数即可。

每一层分出a个分支，一共分解了log_bn次（共log_bn+1层），因此解决问题总代价为：

而每一层分解合并的代价，为该层节点数（非叶节点）a^{{k}乘以f(n/b}k)，其中k为第几层。

因此总共代价为T(n)=n^{{log_ba}+\sum_{k=0}}{log_bn-1}a^kf(n/bk)，从而最终T(n)的渐进界是由其表达式中两部分增长趋势决定的，主定理法正是基于这样的思想。

二、代入法

递归树法中谈到，例子：

[图片上传失败...(image-7339c1-1663928156824)]

的准确答案是T(n)=\Theta(nlogn)，为渐进紧确界，本节将证明这一点

形式化定义

复习一下，渐进紧确界T(n)=\Theta(nlogn)的定义为：

渐进上界和下界只需取渐进紧确界定义不等式的一半即可。

这里采用数学归纳法证明：

证明右侧不等号：

假设命题在小于n时都成立，则等于n时有:

因此只需c_2(log4-\frac{3}{4}log3) -1\ge 0，解得c_2\ge \frac{1}{log4-\frac{3}{4}log3}\ge 0

结合归纳基础的结果，c_2\ge max{\frac{1}{log4-\frac{3}{4}log3},\frac{1}{3log3}}

证明左侧不等号与证明右侧过程一致，结果为0\le c_1\le min{\frac{1}{log4-\frac{3}{4}log3},\frac{1}{3log3}}，此处不再赘述。

综上：T(n)=\Theta(nlogn)

三、主定理法

在递归树法中已经初步介绍主定理法的思想由来，是针对与形如

其递归树解析过程如下：

[图片上传失败...(image-e43019-1663928156824)]

这里再来计算一次总时间复杂度

首先对于合并解分解问题的时间复杂度，需要统计每一层的该类复杂度的加和：

注意这里是从0取到log_bn-1，这是因为最后一层的问题规模为n/b^{{log_bn}，但是并不存在f(n/b}{log_bn})的分解合并代价，所以不会取到log_bn。

而对于解决问题的时间复杂度，只需要看叶子结点个数即可：

因此总的时间复杂度为

因此，从理论上分析，只需要判断T_{分解合并}和T_{解决问题}的趋势大小，就能判断谁是T(n)的主要决定因素。这里不加证明的给出该思路的分析结果

[图片上传失败...(image-11743f-1663928156824)]

该结论的分类，可以图示如下：

[图片上传失败...(image-702615-1663928156824)]

对于该普通形式的主定理，有以下两点需要注意：

1. 分类图示中的大小关系并非简单的大小关系，而是级数大小关系。假设f(n)=nlog(n)，显然有的是nlogn>n，但却不存在 \epsilon 使得f(n)=\Omega(n^{{log_ba+\epsilon})。究其原因，是logn与n}\epsilon不属同一级数。从这一点可以理解到，在分类图示中，存在一个gap（见下图）

   [图片上传失败...(image-4d8920-1663928156824)]

2. 主定理的第一种情况，除了要满足f(n)=\Omega(n^{log_ba+\epsilon})，还要满足“正则条件”：

   

主定理的简化形式

对形如T(n)=aT(n/b)+n^k的递归式，主定理可化简如下：

[图片上传失败...(image-88841b-1663928156824)]

不要忘了注意事项

主定理的扩展形式

普通形式的注意事项中谈到，对于f(n)=nlogn是无法处理的，因为落入了三种情况间的gap中，从而不属于任何一个情况，那么此时，就可以通过扩展形式来解决