文章详情

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

请输入下面的图形验证码

提交验证

短信预约提醒成功

Java 精炼解读时间复杂度与空间复杂度

2024-04-02 19:55

关注

前言:

所谓的复杂度就是衡量算法的效率,衡量算发效率又分为两种,一种叫做时间复杂度,一种叫做空间复杂度。

一、算法效率

算法效率分析分为两种:第一种是时间效率,第二种是空间效率。时间效率被称为时间复杂度,而空间效率被 称作空间复杂度。 时间复杂度主要衡量的是一个算法的运行速度,而空间复杂度主要衡量一个算法所需要的额 外空间,在计算机发展的早期,计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的 迅速发展,计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复 杂度。

二、时间复杂度

1.时间复杂度概念

一个算法所花费的时间与其中语句的执行次数成正比例,算法中的基本操作的执行次数,为算法的时间复 杂度。也就是说当我们拿到一个代码,来看这个代码的时间复杂度的时候,主要是去找这个代码当中执行语句次数最多的代码执行了多少次。

2.大O的渐进表示法

看图分析:

当N的值越来越大,2N和10的值就可以忽略不记了。 

实际中我们计算时间复杂度时,我们其实并不一定要计算精确的执行次数,而只需要大概执行次数,那么这里 我们使用大O的渐进表示法。

 大O符号(Big O notation):是用于描述函数渐进行为的数学符号。

1、用常数1取代运行时间中的所有加法常数。

2、在修改后的运行次数函数中,只保留最高阶项。

3、如果最高阶项存在且不是1,则去除与这个项目相乘的常数。得到的结果就是大O阶。

通过上面我们会发现大O的渐进表示法去掉了那些对结果影响不大的项,简洁明了的表示出了执行次数。

另外有些算法的时间复杂度存在最好、平均和最坏情况:

最坏情况:任意输入规模的最大运行次数(上界)

平均情况:任意输入规模的期望运行次数

最好情况:任意输入规模的最小运行次数(下界) 

例如:在一个长度为N数组中搜索一个数据x

最好情况:1次找到

最坏情况:N次找到

平均情况:N/2次找到 

在实际中一般情况关注的是算法的最坏运行情况,所以数组中搜索数据时间复杂度为O(N)

计算时间复杂度  

例题1:

基本操作执行了2N+10次,通过推导大O阶方法知道,时间复杂度为 O(N)

例题2:

基本操作执行了M+N次,有两个未知数M和N,时间复杂度为 O(N+M)

例题3:

基本操作执行了100次,通过推导大O阶方法,时间复杂度为 O(1)

例题4:计算冒泡排序的时间复杂度

基本操作执行最好N次,最坏执行了(N*(N-1))/2次,通过推导大O阶方法+时间复杂度一般看最坏, 时间复杂度为 O(N^2

例题5:二分查找的时间复杂度

基本操作执行最好1次,最坏O(logN)次,时间复杂度为 O(logN) ps:logN在算法分析中表示是底数 为2,对数为N。有些地方会写成lgN。(建议通过折纸查找的方式讲解logN是怎么计算出来的)(因为二 分查找每次排除掉一半的不适合值,一次二分剩下:n/2 两次二分剩下:n/2/2 = n/4)

例题6:计算阶乘递归的时间复杂度

递归的时间复杂度 = 递归的次数*每次递归执行的次数

通过计算分析发现基本操作递归了N次,时间复杂度为O(N)。

例题7:计算斐波那契递归的时间复杂度

通过计算分析发现基本操作递归了2^N次,时间复杂度为O(2^N)。

规律: 

 2^0+2^1+2^2+2^3……2^(n-(n-1))

等比数列求和

 a1就代表第一项,q是等比就是2,1(1-2^n)/-1,相当于2^n+1,所以时间复杂度为O(2^n)

三、空间复杂度 

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度 。空间复杂度不是程序占用了多少bytes 的空间,因为这个也没太大意义,所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟实践复杂度 类似,也使用大O渐进表示法。

 例题1:计算冒泡排序的空间复杂度

使用了常数个额外空间,所以空间复杂度为 O(1)

 例题2:计算斐波那契的空间复杂度

动态开辟了N个空间,空间复杂度为 O(N)

例题3:计算阶乘递归的空间复杂度

  递归调用了N次,开辟了N个栈帧,每个栈帧使用了常数个空间。空间复杂度为O(N)

总结:

本文简单介绍了什么是时间复杂度、空间复杂度,通过简单例题的方式加深对数组的理解。上述就是今天的内容,有任何疑问的话可以随时私信我,文章哪里出现了问题我都会积极改正,也希望大家能更快的掌握自己想要的知识,让我们一起加油!!!!!

到此这篇关于Java 精炼解读时间复杂度与空间复杂度的文章就介绍到这了,更多相关Java 时间复杂度内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网!

阅读原文内容投诉

免责声明:

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

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

软考中级精品资料免费领

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

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

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

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

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

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

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