(转)递归算法的时间复杂度终结篇与Master method

开篇前言：为什么写这篇文章？笔者目前在学习各种各样的算法，在这个过程中，频繁地碰到到递归思想和分治思想，惊讶于这两种的思想的伟大与奇妙的同时，经常要面对的一个问题就是，对于一个给定的递归算法或者用分治思想缩小问题规模的算法，如何求解这个算法的时间复杂度呢？在google过很多的博文后，感觉这些博文总结的方法，有很好优秀的地方，但是都不够全面，有感于此，笔者决定总结各家之长，作此博文，总结各种方法于此，有不足之处，欢迎各位批评指证！

在算法的分析中，当一个算法中包含递归调用时，其时间复杂度的分析会转化成为一个递归方程的求解。而对递归方程的求解，方法多种多样，不一而足。本文主要介绍目前主流的方法：代入法，迭代法，公式法，母函数法，差分方程法。

---

【代入法】代入法首先要对这个问题的时间复杂度做出预测，然后将预测带入原来的递归方程，如果没有出现矛盾，则是可能的解，最后用数学归纳法证明。

【举   例】我们有如下的递归问题：T(n)=4T(n/2)+O(n)，我们首先预测时间复杂度为O(n²),不妨设T(n)=kn²（其中k为常数），将该结果带入方程中可得：左=kn²，右=4k(n/2)²+O(n)=kn²+O(n),由于n²的阶高于n的阶，因而左右两边是相等的，接下来用数学归纳法进行验证即可。

---

【迭代法】迭代法就是迭代的展开方程的右边，直到没有可以迭代的项为止，这时通过对右边的和进行估算来估计方程的解。比较适用于分治问题的求解，为方便讨论起见，给出其递归方程的一般形式：

【举   例】下面我们以一个简单的例子来说明：T(n)=2T(n/2)+n²,迭代过程如下：

容易知道，直到n/2^(i+1)=1时，递归过程结束，这时我们计算如下：

到这里我们知道该算法的时间复杂度为O(n²)，上面的计算中，我们可以直接使用无穷等比数列的公式，不用考虑项数i的约束，实际上这两种方法计算的结果是完全等价的，有兴趣的同学可以自行验证。

---

【公式法】这个方法针对形如：T(n) = aT(n/b) + f(n)的递归方程。这种递归方程是分治法的时间复杂性所满足的递归关系，即一个规模为n的问题被分成规模均为n/b的a个子问题，递归地求解这a个子问题，然后通过对这a个子问题的解的综合，得到原问题的解。这种方法是对于分治问题最好的解法，我们先给出如下的公式：

公式记忆：我们实际上是比较n^log_ba和f(n)的阶，如果他们不等，那么T(n)取他们中的较大者，如果他们的阶相等，那么我们就将他们的任意一个乘以logn就可以了。按照这个公式，我们可以计算【迭代法】中提到的例子：O(f(n))=O(n²),容易计算另外一个的阶是O(n),他们不等，所以取较大的阶O(n²)。太简单了，不是吗？

需要注意：上面的公式并不包含所有的情况，比如第一种和第二种情况之间并不包含下面这种情况：f(n)是小于前者，但是并不是多项式的小于前者。同样后两种的情况也并不包含所有的情况。为了好理解与运用的情况下，笔者将公式表述成如上的情况，但是并不是很严谨，关于该公式的严密讨论，请看这里。但是公式的不包含的情况，我们很少很少碰到，上面的公式适用范围很广泛的。

特别地，对于我们经常碰到的，当f(n)=0时，我们有：

---

【母函数法】母函数是用于对应于一个无穷序列的幂级数。这里我们解决的递归问题是形如：T(n)=c₁T(n-1)+c₂T(n-2)+c₃T(n-3)+...+c_kT(n-k)+f(n)。为说明问题简便起见，我们选择斐波那契数列的时间复杂度作为例子进行讨论。

【举  例】斐波那契数列递归公式：T(n)=T(n-1)+T(n-2)。这里我们假设F(n)为第n项的运算量。则容易得到：F(n)=F(n-1)+F(n-2),其中F(1)=F(2)=1.我们构造如下的母函数：G(x)=F(1)x+F(2)x²+F(3)x³+......,我们可以推导如下：

上面的方法计算相对来说是比较简单的，关键在于对于母函数的理解，刚开始的时候可能不是很好理解，对于母函数可以参考这里和维基百科这里。

---

【差分方程法】可以将某些递归方程看成差分方程，通过解差分方程的方法来解递归方程，然后对解作出渐近阶估计。这里我们只考虑最长常见的递归形式，形如：T(n)=c₁T(n-1)+c₂T(n-2)+c₃T(n-3)+...+c_kT(n-k)+f(n)，其中c1,c2,...ck为常数且不等于0；我们对该方程的求解如下：

对应上面的齐次方程的特征方程为：

如果解得t=r是该特征方程的m重根，则这m个解的形式为：{rⁿ     n*rⁿ      n²rⁿ   ...    n^m-1rⁿ},其余的关于复数解的形式和普通的线性方程组的形式类似，不再赘述。接下来，我们要求解该方程的对应非齐次方程组的通解，这里我们针对该方程的特殊形式，不加证明地给出如下的通解形式：

则和线性代数中的解一样，原方程的解等于齐次方程组的通解+特解，即：

最后由初始条件确定a(i)的值即可。

为了帮助理解，我们举两个例子看看，就明白是怎么回事了。

【举 例1】递归方程如下：

(1)写出对应齐次方程的特征方程：

得到基础解系为：{t₁ⁿ,  t₂ⁿ}

(2)计算特解，对于本题，直接观察得特解为：-8

(3)得到原方程解的形式为：T(n)=a₀t₁ⁿ+a₁t₂ⁿ-8

(4)代入n=0，n=1的情况，得到a0,a1，最后可得:

可以看到该方程形式和上面讨论过的斐波那契数列只差一个常数8，因而两者的时间复杂度是相同的。有兴趣的同学可以按照这个方法再次计算斐波那契数列的时间复杂度验证一下。

【举  例2】递归方程如下：

（1）计算对应齐次方程的基础解析：

特征方程为：C(t)=t^2-4t-4=0,得到一个2重根t=2.因而其基础解为：{2ⁿ      n*2ⁿ}

（2）由于f(n)=n*2ⁿ，对应上面表格的最后一种情况，得到特解形式为：T(n)=n²(p₀+p₁n)2ⁿ代入原递归方程可得：p0=1/2,p1=1/6

（3）原方程解的形式为：T(n)=a₀*2ⁿ+a₁*n*2ⁿ+n²(1/2+n/6)2ⁿ,代入T(0),T(1)得：a0=a1=0

（4）综上：T(n)=n²(1/2+n/6)2ⁿ

因而时间复杂度为：O(n³2ⁿ)

---

快速排序算法的时间复杂度分析[详解Master method]