在总结递归算法的时间复杂度分析之前，应该明确几组概念。   算法仅仅是求解问题的解决方案，这个解决方案本身并不是问题的答案，而是能获得答案的指令序列。只有通过执行算法才可以获得求解问题的答案。   从算法是否递归调用的角度看，算法可以分为非递归算法和递归算法。   非递归算法时间复杂度分析较为简单，通常是计算算法中基本语句执行次数，一般都是一个关于问题规模n的表达式，然后用渐近符号 Θ、O、o、Ω、ω 表示出算法的时间复杂度。   递归算法是采用分治的方法，把一个“大问题”分解出若干个相似的“小问题”求解。在分析算法复杂度时，关键是根据递归过程建立递推关系式，然后求解递推关系式，得到算法执行的时间表达式（一般都与问题规模n相关），最后用渐近符号 Θ、O、o、Ω、ω 表示出算法的时间复杂度。   在《算法导论》、《算法设计与分析》这2门课中，我们已经学习一些通用的算法设计技术，如增量法、分治法、贪心法、动态规划、线性规划、回溯法、分支限界法等；在算法设计完成后，对算法的复杂度进行分析是必然的，所以本篇的中心将围绕算法时间复杂度展开。

例1：如果算法的执行时间不随着问题规模n的增加而增长，它的基本语句执行的次数是固定的，总的时间由一个常数来限界。此类算法的时间复杂度是O(1)。 例2：当有若干个循环语句时，时间复杂度是由嵌套层数最多的循环语句中的基本语句的执行次数决定。如下

  忽略求解细节。在我们求解递归式时，因为最终是要求得一个时间上限，所以在求解时常常省略一些细节。比如mergeSort(a,0,n-1)运行时间的实际递归式应该是：

  类似的，我们也可以用迭代法求解汉诺塔递归求解时的时间复杂度。但遗憾的是，迭代法一般适用于一阶的递推方程。对于二阶及以上（即 T(n)依赖它前面更多个递归项 ）的递推方程，迭代法将导致迭代后的项太多，从而使得求和公式过于复杂，因此需要将递推方程化简，利用差消法等技巧将高阶递推方程化为一阶递推方程。如在求快速排序算法平均时间复杂度 T(n) 的递推方程， T(n) 依赖 T(n−1)、T(n−2)、...、T(1) 等所有的项，这样的递推方程也称为全部历史递推方程。（这里省略快速排序算法平均复杂度T(n)的求解过程）

小结：上面6种递推关系是高中、本科知识，在此重点介绍了迭代法，其它几种方法虽未在本篇中使用，但可以加深对递推式求解的认识。

代入法实质上就是数学归纳法，因此求递推式分为两步：

  遗憾的是并不存在通用的方法来猜测递归式的正确解，需要凭借经验，偶尔还需要创造力。即使猜出了递归式解的渐近界，也有可能在数学归纳证明时莫名其妙的失败。正是由于该方法技术细节较为难掌握，因此这个方法不适合用来求解递归方程，反而比较适合作为其他方法检验手段。在此不做总结。可以翻阅《算法导论》进行学习。

  递归树是一棵结点带权值的树。初始的递归树只有一个结点，它的权标记为 T(n) ；然后按照递归树的迭代规则不断进行迭代，每迭代一次递归树就增加一层，直到树中不再含有权值为函数的结点（即叶结点都为 T(1) ）。下面以递归方程

  在得到递归树后，将树中每层中的代价求和，得到每层代价，然后将所有层的代价求和，得到所有层次的递归调用的总代价。在上图(d)部分中，完全展开的递归树高度为 lgn (树高为根结点到叶结点最长简单路径上边的数目)，所有递归树具有 lgn+1 层，所以总代价为 cn∗(lgn+1) ，所有时间复杂度为 Θ(nlgn) 。

  总结：递归树模型求解递归方程，本质上就是迭代思想的应用，利用递归方程迭代展开过程构造对应的递归树，然后把每层的时间代价进行求和。不过递归树模型更直观，同时递归树也克服了二阶及更高阶递推方程不方便迭代展开的痛点。

  主方法为如下形式的递归式提供了一种“菜谱”式的求解方法，如下所示

其中 a≥1 和 b>1 是常数， f(n) 是渐近正函数。这个递推式将规模为n的问题分解为a个子问题，每个子问题的规模为 n/b ，a个子问题递归地求解，每个花费时间 T(n/b) 。函数 f(n) 包含了问题分解和子问题解合并的代价。同样，这个递归式也没有考虑上取整、下取整、边界条件等，结果不会影响递归式的渐近性质。

定理4.1(主定理) 令a≥1和b>1是常数， f(n) 是一个函数， T(n) 是定义在非负整数上的递归式：