7.递归函数的复杂度分析-灵析社区

递归函数本质上是对树形结构或者图形结构的深度优先遍历。如果我们能够很清楚我们所设计的算法只访问了树形结构或者图形结构中的每个结点有限次，那么递归函数的时间复杂度就等于树形结构或者图形结构的结点个数。

另外，分析递归函数的时间复杂读还有一个工具，称为「主定理」。由于「主定理」的理论性很强，只需要知道结论，会应用即可。在面试的时候，绝大多数情况下，不会考察主定理的内容和证明。我严谨的论述请参考《算法导论》第 4.5 节和第 4.6 节的内容。

如果一个规模为 n 的问题，可以拆解为 a 个子问题，每个子问题的规模是 b/n，其中 a≥1，b>1。用 f(n) 表示分解和合并的开销与 n 的关系，那么原始问题的时间复杂度 T(n) 可以表示成如下递归式：T(n)=a⋅T( b/n )+f(n)

将此递推式得到关于 n 的通项公式的时候，需要利用以下结论：

证明过程请参考《算法导论》第 4.6 节（证明主定理）。结论可以这样记忆：

比较 f(n) 与 n ^{log ba} 的大小，如果相等，T(n) 等于 log^ba后面乘以 logn。如果不相等，谁大就以谁作为时间复杂度，这一点与「时间复杂度考虑最差情况」的规则一致。