文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

C语言数据结构与算法时间空间复杂度实例分析

2023-06-29 05:07

关注

这篇文章主要介绍“C语言数据结构与算法时间空间复杂度实例分析”的相关知识,小编通过实际案例向大家展示操作过程,操作方法简单快捷,实用性强,希望这篇“C语言数据结构与算法时间空间复杂度实例分析”文章能帮助大家解决问题。

时间复杂度

来看第一个:

long Func(n){return n<2?n:Func(n-1)*n ;}

我们求递归阶乘Func的时间复杂度,说里面 n 最后要到1,我们可以认为递归了多少次就他就计算了多少次,我们稍加思索就可以看出他的时间复杂度是 O(N)。严格来说,递归算法怎么计算呢?

是递归次数 &times; 每次递归的函数的次数

这个每次递归函数的次数是个什么鬼呢?我们的三目操作符在递归中每次会走一次,也就是这个函数会出现一次,就是所谓的常数次嘛 O(1),递归了n次,自然就是O(N)了。如果我再在前面加上个 while(n&ndash;),又是一个执行n次的循环,相当于是在嵌套循环了,这是复杂度就是里外都O(N),为O(N^2)。

再来

long Func(n){return n<2?n:Func(n-1)+(n-2); }

这是斐波那契的递归数列,乍一看和上面的阶乘没太大区别,还是在算他递归了多少次,但是这下可没那么好算了捏。这时我们可以拿起笔画一画多半就有个谱了

C语言数据结构与算法时间空间复杂度实例分析

最后结果一定会让n走到 1,这个是总数的 n ,2^n的 n 只是一个参数,会发现每一层都会满足等比数列关系,有 2的(n-1)次方的累加 = 2的n次方 - 1,这里1可以忽略就是2的n次方。

但是!完了吗?我们格局打开

这里的-1,是要每一层都是满的才满足,但是实际上不满,我们 n,n-1,n-2&hellip;&hellip;最后是1没毛病;我们到其他路线上,n-2,n-3,n-4&hellip;&hellip;压根儿到不了最后一行,在他头上提早结束,后面的同理,也就是说我们整个流程图在后面会有一大坨空白部分,没有调用次数捏。但是!就算缺吧,这些漏网份子依然相对于整体而言非常的小,影响不大,估算角度他依然是2^n。

其实际图像应该是个三角形:

C语言数据结构与算法时间空间复杂度实例分析

格局继续打开

那么如果是2的n次方,那么你将见证一个计算时间复杂度的极端,要知道算法中二分查找是非常快的,要在10亿对象中找一个只需要 log2^1000000000,即30秒左右。

但是上面的斐波那契运行起来可谓慢的令人发指,我在之前在学习C语言递归时就在vs2019上试过,当n = 10时,1000次,小儿科秒出;n = 30时,十亿次,很快啊,看来CPU是有备而来,n = 50时,可以说久了去了,整个程序没有卡死胜似卡死。

看看咱CPU运行速度是多少赫兹可以换算运行速度,一般民用配置高一点点的能达到一秒十亿次计算,别看n只是涨了一点点,电脑寿命够长就给n整个80,你的寿命够长就可以给n整个100。

我们使用递归搞斐波那契会有许多重复,我们改进一下:

# include<stdio.h># include<malloc.h>long long*Func(n){long long* Farr= malloc(sizeof(long long)*(n+1));Farr[0] = 0;if(n==0)  // 防止n=0时发生越界{return Farr;}Farr[1] = 1;}

这个算法就是有前面就能推后面,再看看时间复杂度是O(N),这个优化简直就是质的优化,这个思想就是以空间换时间,开了一个数组,都用了空间,但是性能更快了。

空间复杂度

说是空间复杂度,和空间也不沾关系,他计算的是大概定义的变量的个数,实际意义里面就算是结构体大不了你几十个字节嘛,也没必要去整烂活搞几万个字节出来。我小小 8个G,几十亿字节,你占用我几字节,几百字节,几千字节我压根儿不甩你,所以为什么不谈空间大小谈个数。

可能如今就只有嵌入式比较介意空间,因为嵌入式通常是在一些设备上面,举个栗子就是我们常见的智能居家AI,一个吸尘器机器人会用到的探测器算法,内存条占用多了机器咋安是吧,不是内存贵是空间有限

我们就拿刚刚的阶乘来说,从n开始,会建立一个栈帧,每调用一次递归就要创建一个栈帧,每个栈帧里面空间是常数个,调用了n次,那么空间复杂度就是常数&times;n为O(N)。

关于“C语言数据结构与算法时间空间复杂度实例分析”的内容就介绍到这里了,感谢大家的阅读。如果想了解更多行业相关的知识,可以关注编程网行业资讯频道,小编每天都会为大家更新不同的知识点。

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯