关于递归的时间复杂度分析

### 引言 基于循环的算法的时间复杂度通常比较容易分析。例如用于求最短路径的Bellman-Ford算法，由于两层循环，它的时间复杂度为$\Theta(NM)$。 相比之下，递归算法的时间复杂度分析起来会更难一些。我们常用的许多算法都有递归调用，其中分治法是递归算法的一大类。 多数递归算法都有这几点特征：当处理一个问题时，先将它分解成几个规模更小的子问题，分别递归求解子问题，最后处理子问题的结果得到答案。当问题足够小时，就可以不用分解直接得到答案，即递归存在边界。 下面举出几个具体例子，分析这类算法的时间复杂度。 ### ① 归并排序 对数组$A$的某个区间$[l,r]$排序。 我们可以选取$mid=\lfloor\frac{l+r}{2}\rfloor$，递归对区间$[l,mid]$和$[mid+1,r]$排序，然后对两个有序的区间进行归并。 递归的一个边界是$l=r$，即区间长度为$1$时无需排序。 记排序长度为$n$的区间所需的时间为$f(n)$，因为每次分成两个子问题，子问题的规模缩小一半，归并需要$\Theta(n)$的时间，可以得到以下递归式： $f(n)=\Theta(n)+2f(\frac{n}{2}),n>1$ $f(1)=\Theta(1)$ **注意**：上面给出的递归式省略了取整符号。正常情况下，归并排序的时间复杂度递归式应该为 $f(n)=\Theta(n)+f(\lfloor\frac{n}{2}\rfloor)+f(\lceil\frac{n}{2}\rceil),n>1$ ，为了计算方便，我们只考虑$n$为$2$的整数幂的情况，也就省略了取整符号。这对最后得出的时间复杂度渐进表示没有影响。下面的例子也同样。 ### ② Strassen算法 Strassen算法是用来求矩阵乘法的分治算法。对于两个$n\times n$的矩阵相乘，它将每个矩阵分解为四个$\frac{n}{2}\times\frac{n}{2}$的小矩阵，利用这些小矩阵计算出十个$\frac{n}{2}\times\frac{n}{2}$矩阵的和或差，然后递归七次计算矩阵乘法，最后用子问题得到的矩阵加减运算得到答案。分解子问题和归并都需要$\Theta(n^2)$的时间。递归的边界为$n=1$。 它的时间复杂度递归式是： $f(n)=\Theta(n^2)+7f(\frac{n}{2}),n>1$ $f(1)=\Theta(1)$ 算法的具体实现这里并不进行讲解。 ### ③ 寻找第k大 在一个数组$A$的某个区间$[l,r]$上，寻找第$k$大的值。 我们可以随便选取一个在$[l,r]$里出现过的值$mid$，并用$\Theta(n)$的时间把所有小于$mid$的元素交换到$mid$左边，所有大于$mid$的元素交换到右边（就像快速排序那样）。此时可以得到$mid$的排名$p$，如果$k<p$则递归寻找左区间的第$k$大，$k>p$则递归寻找右区间的第$k-p$大，否则直接返回$mid$。递归的一个边界是$l=r$。 由于平均情况下我们可以把子问题缩小一半（这其实是不严谨的，这里举这个例子仅仅为了引出递归式，后面我们会用另一种方法推导它的平均复杂度），依然可以得到递归式： $f(n)=\Theta(n)+f(\frac{n}{2}),n>1$ $f(1)=\Theta(1)$ ### 一般形式的数学推导 对于以上两个递归式，都可以变形为一个更一般的形式： $f(n)=\Theta(n^t)+kf(\frac{n}{m}),n>1$ $f(1)=\Theta(1)$ 其中参数的取值范围$t\ge0,m>1,k>0$ 如何用数学方法得到这个递归式的渐进表示？ 首先，我们可以移去对最后结果没有影响的渐进符号（不严谨地说，渐进符号其实就是乘了一个常数）。即 $f(n)=n^t+kf(\frac{n}{m}),n>1$ $f(1)=1$ 这样$f(n)$变成了一个关于$n$的确定的函数。上文已经说到，因为省略了取整符号，只考虑$n$为$m$的整数幂的情况。于是： $f(1)=1$ $f(m)=k+m^t$ $f(m^2)=k^2+km^t+m^{2t}$ ...... $f(m^a)=k^a+k^{a-1}m^t+...+km^{(a-1)t}+m^{at}=\sum_{i=0}^{a}k^{a-i}m^{it}$ 这是一个等比数列的求和，它的公比是$\frac{m^t}{k}$。 不过我在这里并不想使用等比数列的求和公式。我要使用的是这个： $1+x+x^2+x^3+...=\frac{1}{1-x},0<x<1$ 这个公式表示的是一个公比小于$1$的正项等比数列无穷项的和。它还告诉我们，这个数列前任意项的和一定小于某个常数（利用上面的结论），因为公比是确定的。 回到刚才的$f(m^a)$上来。因为公比$\frac{m^t}{k}$是一个确定的常数，如果它小于$1$，那么$f(m^a)$一定小于$k^a$乘以某个常数。所以$f(m^a)=\Theta(k^a)$。 令$m^a=n$，则有$f(n)=\Theta(k^{log_mn})=\Theta(n^{log_{m}k}),m^t<k$。 这样我们就可以解决第二个例子Strassen算法的时间复杂度：把$t=2,k=7,m=2$代入，即有$f(n)=\Theta(n^{log_{2}7})$。 接下来讨论公比$\frac{m^t}{k}=1$的情况。很明显等比数列的所有项都相等，一共有${log_mn}+1$项，总和为$({log_mn}+1)n^t=\Theta(n^tlogn)$。 这种情况对应第一个例子归并排序，把$t=1,k=2,m=2$代入，即有$f(n)=\Theta(nlogn)$。 只剩下最后一种情况，$\frac{m^t}{k}>1$。 考虑等比数列求和正反求都一样，可以把整个数列反着写，于是形成了一个新的等比数列，它的首项是原数列的末项，公比是原数列的倒数。 再次应用上面的结论，我们得到： $f(n)=\Theta(m^{at})=\Theta(n^t),m^t>k$。 这对应了第三个例子：代入$t=1,k=1,m=2$，得到 $f(n)=\Theta(n)$ ### 综上所述 对于以下形式的递归式 $f(n)=\Theta(n^t)+kf(\frac{n}{m}),n>1$ $f(1)=\Theta(1)$ $t\ge0,m>1,k>0$ 有 $f(n)=\Theta(n^{log_{m}k}),m^t<k$ $f(n)=\Theta(n^tlogn),m^t=k$ $f(n)=\Theta(n^t),m^t>k$ ### 随机数据与平均复杂度 很多情况下，子问题的规模并不是确定的。例如上面的例子“寻找第k大”，当处理长度为$n$的区间时，子问题的规模是$1$到$n-1$中的一个数，它取决于数据，包括k的值和每次选择的mid值。 在最坏情况下，子问题的规模一直是$n-1$，递归式会变为 $f(n)=\Theta(n)+f(n-1)=\Theta(n^2)$ 但是，通常情况下，最坏情况出现的概率极低，我们关心的是其在随机数据下的平均复杂度。 如果数据是随机数据，k也是随机取的，那么子问题的规模就会是$[1,n-1]$中的一个随机值，且子问题的$k$也是随机值。 那么，我们会得到下面的递归式： $f(n)=\Theta(n)+\overline{f}(n),n>1$ $f(1)=\Theta(1)$ 其中$\overline{f}(n)=\frac{\sum_{i=1}^{n-1}f(i)}{n-1}$表示$f(1)$到$f(n-1)$的平均值。 ### 数学归纳法 对于这个递归式，依然移去渐进符号： $f(n)=n+\overline{f}(n),n>1$ $f(1)=1$ 容易看出$f(n)=2n-1$，证明也比较简单，简单粗暴的数学归纳法： 设对于任意$n_0<n$满足$f(n_0)=2n_0-1$，则 $\overline{f}(n)=\frac{\sum_{i=1}^{n-1}f(i)}{n-1}=\frac{n(n-1)-(n-1)}{n-1}=n-1$ $f(n)=n+\overline{f}(n)=2n-1=\Theta(n)$ 又因$f(1)=1$，结论得证。 考虑另一个问题，把上面的递归式改为$f(n)=n+2\overline{f}(n)$ 我们猜想$f(n)=\Theta(nlogn)$，尝试用数学归纳法证明： 设对于任意$n_0<n$满足$f(n_0)\le cn_0log(n_0)+a$，欲证$f(n)\le cnlog(n)+a$ 不太好弄，可以玩一个小技巧，因为$\sum_{i=1}^n\frac{1}{i}=\Theta(logn)$，定义$d(n)=\sum_{i=1}^n\frac{1}{i}$，并用$d(n)$换原式中的$log(n)$ 设对于任意$n_0<n$满足$f(n_0)\le cn_0d(n_0)$ 经过计算$2\overline{f}(n)\le cnd(n)-\frac{cn}{2}$ 只要$c\ge2$，即有$f(n)\le cnd(n)=\Theta(nlogn)$ 又$f(1)\le c$，结论得证。 其实$f(n)=2nd(n)-n$ ### 结语 递归算法多种多样，时间复杂度的推导也各不相同。这里举了几种简单的例子，其他的情况还需大家思考。 如有错误，还请各位指正