Question

递归时间复杂度 推演计算

Answer 1

递归的时间复杂度计算较为麻烦。以下我们使用归并排序的例子，对递归复杂度进行推演。

假设现在有一个归并排序。他的运行总时间是 T（n） ，
我们通过将其分解成 2 个计算式，即 ： 2 * （T（n/2））+ n ，为什么加 n 呢？因为 n/2 只是递归计算的时间，实际还有合并的时间，在大部分递归中，不但有子任务的时间，还有合并子任务的时间也要计算（在递归计算中，子问题消耗的时间需要统计，合并子问题的结果所消耗的时间也要统计）。

现在，我们的公式是 2 * （T（n/2））+ n ，表达的是一颗高度是 1 的递归树：

如上图，我们需要把这颗递归树的 3 个节点的所有耗时都加上，最终的结果就是 T(N) ;
再看上图，我们递归了 1 层，如果递归 2 层、3层呢？

递归 2 层，表达式变为 4 *（T（n/4）)+ 2n .

递归 3 层，表达式变为 8 * （T（n/8）)+ 3n .

我们总结一下：

递归 2 层： 4（T（n/4）)+ 2n
递归 3 层： 8（T（n/8）)+ 3n
递归 4 层： 16（T（n/16）)+ 4n
······
递归 k 层： 2^k （T（n/2^k））+ kn

假设我们最终递归的结果是 1，那么：

T(n/2^k) = 1
·····反推 2^k = n
····· 那么 k = log2n

k 等于 log2N ，我们带入 k 到上面的公式： 2^k （T（n/2^k））+ kn ；

即 n + log2n * n ；

使用大 O 表达式，去除常数，低阶，系数，递归的时间复杂度为 O(nlogn) ;

关于递归树的推演，推荐观看一个视频，讲的很详细，地址： https://www.youtube.com/watch?v=bQi9BHCiusg