递归时间复杂度 推演计算
发布网友
发布时间：2022-12-01 21:45
共1个回答
热心网友
时间：2023-11-08 02:22
假设现在有一个归并排序。他的运行总时间是 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.*.com/watch?v=bQi9BHCiusg
