Java数据结构--时间和空间复杂度
一、算法效率
算法效率分析分为两种:时间效率和空间效率
时间效率
时间效率被称为时间复杂度,主要时衡量一个算法的运行速度
空间效率
空间效率被称为空间复杂度,主要衡量一个算法所需要的额外空间
二、时间复杂度
1. 概念
一个算法所花费的时间与其中语句的执行次数成正比,故将算法中的基本操作的执行次数,作为算法的时间复杂度
并且时间复杂度其实还可以分成三种情况:
- 最坏情况:任意输入规模的最大运行次数
- 平均情况:任意输入规模的期望运行次数
- 最好情况:任意输入规模的最小运行次数
而在实际中一般关注的是算法的最坏运行情况
2. 大 O 的渐进表示法
实际在我们计算时间复杂度时,并不一定要计算精确的执行次数,而只需要大概执行次数,故我们使用大 O 的渐进表示法(大 O 符号是用于描述函数渐进行为的数学符号)
使用方法
用常数1取代运行时间中的所有加法常数在修改后的运行次数函数中,只保留最高阶项如果最高阶项存在且不为1,则去除与这个项目相乘的常数
如某个算法的基本操作次数为 F(N) = N^2^ + 2*N + 10,用大 O 的渐进表示法为:O(N)
3. 练习
在这里放入两个递归函数的练习,我们来试着推导其的时间复杂度
练习一:计算阶乘递归 factorial 的时间复杂度
long factorial(int N) { return N < 2 ? N : factorial(N-1) * N; }
这题很简单,结果为:O(N)
练习二:计算斐波那契递归 fibonacci 的时间复杂度
int fibonacci(int N) { return N < 2 ? N : fibonacci(N-1)+fibonacci(N-2); }
这题可以结合画图类似于二叉树去思考,结果为:O(N2)
注意
递归的时间复杂度 = 递归的次数 * 每次递归内容要执行的次数
三、空间复杂度
1. 概念
空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度,它不是计算程序占用了多少 byte 的空间,而是计算变量的个数。(空间复杂度也使用大 O 的渐进表示法)
2. 练习
练习一:计算 bubbleSort 的空间复杂度
void bubbleSort(int[] array) { for (int end = array.length; end > 0; end--) { boolean sorted = true; for (int i = 1; i < end; i++) { if (array[i - 1] > array[i]) { Swap(array, i - 1, i); sorted = false; } } if (sorted == true) { break; } } }
因为只使用了常数个额外空间,故结果为:O(1)
练习二:计算 fibonacci 的空间复杂度
int[] fibonacci(int n) { long[] fibArray = new long[n + 1]; fibArray[0] = 0; fibArray[1] = 1; for (int i = 2; i <= n ; i++) { fibArray[i] = fibArray[i - 1] + fibArray [i - 2]; } return fibArray; }
因为动态开辟了 N 个空间,故结果为:O(N)
练习三:计算阶乘递归 Factorial 的时间复杂度
long factorial(int N) { return N < 2 ? N : factorial(N-1)*N; }
因为递归调用了 N 次,开辟了 N 个栈帧,每个栈帧使用了常数个空间,故结果为:O(N)
四、总结
本片文章就到这里了,希望能够给你带来帮助,也希望您能够多多关注猪先飞的更多内容!
相关文章
- 这篇文章主要介绍了如何利用java语言实现经典《复杂迷宫》游戏,文中采用了swing技术进行了界面化处理,感兴趣的小伙伴可以动手试一试...2022-02-01
java 运行报错has been compiled by a more recent version of the Java Runtime
java 运行报错has been compiled by a more recent version of the Java Runtime (class file version 54.0)...2021-04-01- 这篇文章主要介绍了在java中获取List集合中最大的日期时间操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-08-15
- 这篇文章主要介绍了教你怎么用Java获取国家法定节假日,文中有非常详细的代码示例,对正在学习java的小伙伴们有非常好的帮助,需要的朋友可以参考下...2021-04-23
- 这篇文章主要介绍了Java如何发起http请求的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-03-31
- 说起C#和Java这两门语言(语法,数据类型 等),个人以为,大概有90%以上的相似,甚至可以认为几乎一样。但是在工作中,我也发现了一些细微的差别...2020-06-25
mysql中获取一天、一周、一月时间数据的各种sql语句写法
创建表:复制代码 代码如下:create table if not exists t( id int, addTime datetime default '0000-00-00 00:00:00′)添加两条初始数据:insert t values(1, '2012-07-12 21:00:00′);insert t values(2, '2012-07...2014-05-31- 这篇文章主要介绍了.NET/C# 使用Stopwatch测量运行时间,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-06-25
- 这篇文章主要介绍了解决Java处理HTTP请求超时的问题,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-03-29
- 这篇文章主要介绍了C#数据结构之队列(Quene),结合实例形式较为详细的讲述了队列的功能、原理与C#实现队列的相关技巧,需要的朋友可以参考下...2020-06-25
- 这篇文章主要介绍了java 判断两个时间段是否重叠的案例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-08-15
- 这篇文章主要介绍了超简洁java实现双色球若干注随机号码生成(实例代码),本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-04-02
- 这篇文章主要介绍了Java生成随机姓名、性别和年龄的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-10-01
java 画pdf用itext调整表格宽度、自定义各个列宽的方法
这篇文章主要介绍了java 画pdf用itext调整表格宽度、自定义各个列宽的方法,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-01-31- 这篇文章主要介绍了java正则表达式判断前端参数修改表中另一个字段的值,需要的朋友可以参考下...2021-05-07
Java使用ScriptEngine动态执行代码(附Java几种动态执行代码比较)
这篇文章主要介绍了Java使用ScriptEngine动态执行代码,并且分享Java几种动态执行代码比较,需要的朋友可以参考下...2021-04-15- 这篇文章主要介绍了Java开发实现人机猜拳游戏,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-08-03
- 常用的日期时间正则表达式 下面收藏了大量的日期时间正则匹配函数,包括分钟,时间与秒都能达到。 正则表达式 (?n:^(?=d)((?<day>31(?!(.0?[2469]|11))|30(?!.0?2)|29(...2016-11-25
- 实例讲解之前,先来介绍几个核心函数: mktime 函数 mktime() 函数返回一个日期的 Unix 时间戳。 参数总是表示 GMT 日期,因此 is_dst 对结果没有影响。 参数可以从右到左依次空着,空着的参数会被设为相应的当前 GMT 值。...2015-11-08
Java 8 Stream 的终极技巧——Collectors 功能与操作方法详解
这篇文章主要介绍了Java 8 Stream Collectors 功能与操作方法,结合实例形式详细分析了Java 8 Stream Collectors 功能、操作方法及相关注意事项,需要的朋友可以参考下...2020-05-20