递归时间复杂度 递归树 推演计算

递归时间复杂度 递归树 推演计算

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

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

现在,我们的公式是 2 * (T(n/2))+ n,表达的是一颗高度是 1 的递归树:

image.png

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

 2 层

递归 2 层,表达式变为 4 *(T(n/4))+ 2n.

3 层

递归 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


递归时间复杂度 递归树 推演计算
http://thinkinjava.cn/2019/10/19/2019/1019-fuzadujisuan/
作者
莫那·鲁道
发布于
2019年10月19日
许可协议