递归时间复杂度 递归树 推演计算
递归时间复杂度 递归树 推演计算
递归的时间复杂度计算较为麻烦。以下我们使用归并排序的例子,对递归复杂度进行推演。
假设现在有一个归并排序。他的运行总时间是 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)
;
最后
关于递归树的推演,推荐观看一个视频,讲的很详细,
递归时间复杂度 递归树 推演计算
http://thinkinjava.cn/2019/10/19/2019/1019-fuzadujisuan/