引言
基于循环的算法的时间复杂度通常比较容易分析。例如用于求最短路径的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。
考虑等比数列求和正反求都一样，可以把整个数列反着写，于是形成了一个新的等比数列，它的首项是原数列的末项，公比是原数列的倒数。
再次应用上面的结论，我们得到：
这对应了第三个例子：代入$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
结语
递归算法多种多样，时间复杂度的推导也各不相同。这里举了几种简单的例子，其他的情况还需大家思考。
如有错误，还请各位指正