算法:如何借助树来求解递归算法的时间复杂度?
发布日期:2022-03-16 03:25:33 浏览次数:5 分类:技术文章

本文共 5188 字,大约阅读时间需要 17 分钟。

递归树与时间复杂度分析

我们知道,递归代码的时间复杂度分析起来很麻烦。除了可以使用递推公式这种比较复杂的分析方法外,还可以借助递归树来分析递归算法的时间复杂度。

递归的思想就是,将大问题分解为小问题来求解,然后再将小问题分解为小小问题。这样一层一层的分解,直到问题的数据规模被分解得足够小,不用继续递归分解位置。

如果我们把这个一层一层的分解过程画成图,它其实就是一棵树。我们给这棵树起一个名字,叫做递归树。如下图为一颗棵斐波那契数列的递归树,节点里的数字表示数据的规模,一个节点的求解可以分解为左右子节点两个问题的求解。

在这里插入图片描述

分析快速排序的时间复杂度

为什么说用递推公式来求解平均时间复杂度非常复杂

  • 快排在最好情况下,每次分区都能一分为二,这个时候用递推公式 T ( n ) = 2 T ( n 2 ) + n T(n) = 2T(\frac{n}{2}) + n T(n)=2T(2n)+n,很容易就能推导出时间复杂度是 O ( n l o g n ) O(n log n) O(nlogn)。但是,我们并不可能每次分区都这么幸运,正好一分为二。

  • 我们假设平均情况下,每次分区之后,两个分区的大小比例为 。当 时,如果用递推公式的方法来求解时间复杂度的话,递推公式就写成 T ( n ) = T ( n 10 ) + T ( 9 n 10 ) + n T(n) = T(\frac{n}{10} ) + T(\frac{9n}{10} ) + n T(n)=T(10n)+T(109n)+n

这个公式可以推导出时间复杂度,但是推导过程非常复杂。

用递归树来简化快排的平均复杂度为例

  • 我们还是取k等于9,也就是说,每次分区都很不平均,一个分区是另一个分区的9倍。如果我们把递归分解的过程画成递归树,如下图:
    在这里插入图片描述
  • 快排中,每次分区都要遍历待分区区间的所有数据,所以,每一层分区操作所遍历的个数之和就是n。我们现在只要求出递归树的高度h,这个快排过程遍历的数据个数就是h*n,也就是说 O ( n ∗ h ) O(n*h) O(nh)

因为每次分区并不是均匀的一分为二,所以递归树并不是满二叉树。这样一个递归树的高度是多少呢?

  • 我们知道,快排结束的条件就是待排序的小区间,大小为1,也就是说叶子节点里的数据规模是1.从根节点n到叶子节点1,递归树中最短的一个路径每次都乘以 1 10 \frac{1}{10} 101,最长的一个路径每次都乘以 9 10 \frac{9}{10} 109。通过计算,我们可以得到,从根节点到叶子节点的最短路径是 l o g 10 n log_{10}n log10n,最长的路径是 l o g 10 9 n log_{\frac{10}{9}n} log910n
    在这里插入图片描述
  • 所以,遍历数据的个数就介于 n l o g 10 n nlog_{10}n nlog10n n l o g 10 9 n nlog_{\frac{10}{9}n} nlog910n之间。根据复杂度的大0表示法,对数复杂度的底数不管是多少,我们统一写成 l o g n logn logn。所以,当分区大小比例是1:9时,快速排序的时间复杂度仍然是 O ( n l o g n ) O(n log n) O(nlogn)

刚刚我们假设 ,那如果 ,也就是说,每次分区极其不平均,两个区间大小是 ,这个时候的时间复杂度是多少呢?

  • 我们可以类比上面 的分析过程。当 的时候,树的最短路径就是 l o g 100 n log_{100}n log100n,最长的路径是 l o g 100 99 n log_{\frac{100}{99}n} log99100n
  • 所以总遍历数据个数介于 n l o g 100 n nlog_{100}n nlog100n n l o g 100 99 n nlog_{\frac{100}{99}n} nlog99100n之间。尽管底数变了,快速排序的时间复杂度仍然是 O ( n l o g n ) O(n log n) O(nlogn)

也就是说,对于k等于 9,99 ,甚至是999 ,9999 ……,只要k的值不随n变化,是一个事先确定的常量,那快排的时间复杂度就是 O ( n l o g n ) O(n log n) O(nlogn)。所以,从概率学的角度来说,快排的时间复杂度就是 O ( n l o g n ) O(n log n) O(nlogn)

分析归并排序的时间复杂度

如下图,归并排序每次会将数据规模一分为二。其递归树如下:

在这里插入图片描述

  • 因为每次分解都是一分为二,所以代价很低,我们把时间上的消耗记为常量1。归并算法中比较耗时的是归并操作,也就是两个子数组合并为大数组。从图中我们可以看出,每一层归并操作消耗的时间总和是一样的,跟要排序的数据规模有关。我们把每一层归并操作消耗的时间记为n。
  • 现在,我们只需要知道这棵树的高度h,用高度h乘以每一层的时间消耗n,就可以得到总的时间复杂度 O ( n ∗ h ) O(n*h) O(nh)
  • 从归并排序的原理和递归树可以看出来,归并排序递归树是一颗满二叉树。满二叉树的高度是 l o g 2 n log_2n log2n。所以,归并排序实现的时间复杂度就是 O ( n l o g 2 n ) O(nlog_2n) O(nlog2n)

分析斐波那契数列的时间复杂度

对于斐波那契数列:

int f(int n) {
if (n == 1) return 1; if (n == 2) return 2; return f(n-1) + f(n-2);}

其递归树为:

在这里插入图片描述

这棵递归树的高度是多少呢?

  • f ( n ) f(n) f(n)分解为 f ( n − 1 ) f(n-1) f(n1) f ( n − 2 ) f(n-2) f(n2),每次数据规模都是-1或者-2,叶子节点的数据规模是1或者2,。所以,从根节点走到叶子节点,每条路径是长短不一的。如果每次都是-1,那么最长路径大约就是n;如果每次都是-2,那最短路径大约是 n 2 \frac{n}{2} 2n
  • 每次分解之后的合并操作只需要一次加法运算,我们把这次加法运算的时间消耗记作1.所以,从上往下,第一层的总时间消耗是1,第二次的总时间消耗是2,第三层的总时间消耗就是 2 2 2^2 22。依次类推,第 k k k层的时间消耗是 2 k − 1 2^{k-1} 2k1,那整个顺丰的总时间消耗就是每一层时间消耗之和。
  • 如果路径长度都为n,那么这个总和就是 2 n − 1 2^n - 1 2n1
    在这里插入图片描述
  • 如果路径长度都为 n 2 \frac{n}{2} 2n,那整改算法的总的时间消耗是 2 n 2 − 1 2^{\frac{n}{2}}-1 22n1
    在这里插入图片描述

所以,这个算法的时间复杂度就介 O ( 2 n ) O(2^n) O(2n) O ( 2 n 2 ) O(2^{\frac{n}{2}}) O(22n)之间。虽然这样得到的结果还不够精确,只是一个范围,但是我们也基本上知道了上面算法的时间复杂度是指数级的,非常高。

分析全排列的时间复杂度。

所谓全排列就是“如何把n个数据的所有排列都找出来”。

举个例子,比如, 1、2、3这样3个数据,有下面这几种不同的排列:

1, 2, 31, 3, 22, 1, 32, 3, 13, 1, 23, 2, 1

如何编程打印一组数据的所有排列呢?这里就可以用递归来实现。

如果我们确定了最后一位数据,那就变成了求解剩下n-1个数据的排列问题。而最后一位数据可以是n个数据中的任意一个,因为它的取值就有n中情况、所以“n个数据的排列”问题,就可以分解成n个“n-1个数据的排列的”的子问题。

递推公式如下:

假 设 数 组 中 存 储 的 是 1 , 2 , 3... n 假设数组中存储的是 1,2, 3...n 123...n
f ( 1 , 2 , . . . n ) = 最 后 一 位 是 1 , f ( n − 1 ) + 最 后 一 位 是 2 , f ( n − 1 ) + . . . + 最 后 一 位 是 n , f ( n − 1 ) 。 f(1,2,...n) = {最后一位是 1, f(n-1)} + {最后一位是 2, f(n-1)} +...+{最后一位是 n, f(n-1)}。 f(1,2,...n)=1,f(n1)+2,f(n1)+...+n,f(n1)

代码为:

public class Main {
// k 表示要处理的子数组的数据个数 public static void printPermutations(int [] data, int n, int k){
if(k == 1){
for (int i = 0; i < n; ++i){
System.out.print(data[i] + " "); } System.out.println(); } for (int i = 0; i < k; ++i){
int tmp = data[i]; data[i] = data[k - 1]; data[k - 1] = tmp; printPermutations(data, n, k - 1); tmp = data[i]; data[i] = data[k-1]; data[k-1] = tmp; } } public static void main(String[] args) {
int[]a ={
1, 2, 3, 4}; printPermutations(a, 4, 4); }}

时间复杂度分析:

  • 首先,我们还是画出递归树。不过,现在的递归树已经不是标准的二叉树了。
    在这里插入图片描述
  • 第一层分解有 n n n次交换操作,第二层有n个节点,每个节点分解需要n-1次交换,所以第二层总的交换次数是 n ∗ ( n − 1 ) n * (n-1) n(n1)。第三层有 n ∗ ( n − 1 ) n * (n-1) n(n1)个节点,每个节点需要n-2次交换,所以第三层总的交换次数是 n ∗ ( n − 1 ) ∗ ( n − 2 ) n * (n-1) * (n - 2) n(n1)(n2)
  • 以此类推,第 k 层总的交换次数就是 n ∗ ( n − 1 ) ∗ ( n − 2 ) ∗ … ∗ ( n − k + 1 ) n∗(n−1)∗(n−2)∗…∗(n−k+1) n(n1)(n2)(nk+1)。最后一层的交换次数就是 n ∗ ( n − 1 ) ∗ ( n − 2 ) ∗ … ∗ 2 ∗ 1 n∗(n−1)∗(n−2)∗…∗2∗1 n(n1)(n2)21。每一层的交换之和就是总的交换次数。
    n + n ∗ ( n − 1 ) + n ∗ ( n − 1 ) ∗ ( n − 2 ) + . . . + n ∗ ( n − 1 ) ∗ ( n − 2 ) ∗ . . . ∗ 2 ∗ 1 n + n*(n-1) + n*(n-1)*(n-2) +... + n*(n-1)*(n-2)*...*2*1 n+n(n1)+n(n1)(n2)+...+n(n1)(n2)...21
  • 这个公式的求和比较复杂,我们看最后一个数, n ∗ ( n − 1 ) ∗ ( n − 2 ) ∗ … ∗ 2 ∗ 1 n∗(n−1)∗(n−2)∗…∗2∗1 n(n1)(n2)21等于n!,而前面的 n−1 个数都小于最后一个数,所以,总和肯定小于 n ∗ n ! n∗n! nn!,也就是说,全排列的递归算法的时间复杂度大于 O ( n ! ) O(n!) O(n!),小于 O ( n ∗ n ! ) O(n∗n!) O(nn!)

虽然我们没法知道非常精确的时间复杂度,但是这样一个范围已经让我们知道,全排列的时间复杂度是非常高的。

转载地址:https://blog.csdn.net/zhizhengguan/article/details/122435493 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:redis:redis的底层数据结构
下一篇:算法:清晰理解红黑树的演变--红黑的含义

发表评论

最新留言

不错!
[***.144.177.141]2024年02月27日 23时35分54秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

linux服务器上已安装R 用户下载R包,R语言安装R package的2种方法 2019-04-21
linux 7 磁盘空间太小,Linux下磁盘保留空间的调整,解决df看到的空间和实际磁盘大小不一致的问题... 2019-04-21
linux下mysql 备份方法,Linux下mysql数据库备份方法小结 2019-04-21
bootstrap 页面垂直居中_iframe中如何让layer提示框显示在垂直居中的位置 2019-04-21
肺部ct重建_胸片检查容易漏诊肺癌,去年正常今年晚期常发生,体检一定要做CT... 2019-04-21
3dmax如何拆分模型_3D建模大佬如何制作出惊艳四方的游戏建模,看完这篇文章我知道了... 2019-04-21
x86so文件装换成arm64位_64位系统正式发布说明及介绍!! 2019-04-21
for循环中取出最大最小 累加_LeetCode之长度最小的子数组 2019-04-21
如何打开老公人脸识别_【话题】南宁已有小区启用人脸识别门禁,有人点赞有人忧... 2019-04-21
makex机器人程序_机器人教育为相城青少年叩开科学世界大门 2019-04-21
一寸照纯红色底图片_Ella陈嘉桦也是“时髦精”,穿玫红色西装配拼色半身裙,高级洋气... 2019-04-21
米哈游客户端笔试题_Garena校招 游戏客户端开发通关面经 2019-04-21
airpodspro没有弹窗_使用AirPods Pro一天的主观感受 2019-04-21
创建物化视图commit_视图及范式 2019-04-21
函数传参字典_Python新手上车17:函数传递任意多个参数 2019-04-21
去掉数组最后一个元素_【一天一大 lee】在排序数组中查找元素的第一个和最后一个位置 (难度:中等) Day20201201... 2019-04-21
秦九韶算法递推公式_算法讲解之复杂度分析 2019-04-21
添加绝对路径_网站中如何添加绝对路径 2019-04-21
python房价数据分析波士顿代码数据_python数据分析-波士顿房价预测-Go语言中文社区... 2019-04-21
redis线程阻塞原因排插_Redis阻塞原因详解 2019-04-21