java时间复杂度计算_时间复杂度 - Java那些事儿专栏_江平舟的博客-程序员宅基地

技术标签: java时间复杂度计算  

ArrayList部分一共五篇文章了,并且引入了时间复杂度来分析,强烈建议大家一定要按顺序阅读,本文是第3篇,前两篇文章分别是:

最近看了一下评论区里,大家都急着想要了解HashMap,先不要着急,要完整的了解HashMap的内部实现,我们还需要一些基础知识,有了这些基础知识,我们才能更好的理解HashMap,其实我们已经在不知不觉进入了数据结构的大门,为了以后让大家能更好的理解后续文章,本文我们先引入时间复杂度这个概念。

a6fafbd33437a197919f8cd80a332463.png

还是那个Person对象,增加了一个属性年龄

71d9e735d4a61d620f1b4326dc76bd49.png

创建一个数组,并在数组里放了10个Person对象,老规矩,我们上图:

2a064166e17525eb94e95dea7b84f0ad.png

假如我们有这么一个需求,我们想知道小组里周八的年龄,相信大家都会写代码去找:

4213d6f4f89bafcc209d277be8d0a881.png

需要循环取6次从数组里获取Person对象。

这时候小明同学过来说,哎呀,我知道周八在小组的第5个位置(数组下标5),不用循环,我们直接找他就是

6865de72842974aab8869af6f216c279.png

不需要循环,1次就取到了Person对象:

720c4d003bf47811d2249077c7993ba7.png

无论数组中有多少个元素,每次去读取元素和并比较的时间总是相同的,假设这个时间为K,在上面示例中在数组中循环搜索某个用户,我们循环了6次才搜索到该用户,时间为6*K,在效率上来看,前者比后者的方式快了6倍,但这种说法意义不大,因为在实际中,数组可能有100个元素,而这个“周八”有可能在数组的第1个位置,也有可能在最后一个位置。

在现实中,我们用来计算时间的长短,一般单位有小时,分钟,秒等,同样我们也需要一种度量来计算本示例中的算法的效率,在计算机科学中,这种度量方法被称为“大O”表示法。

当我们知道元素的位置,一步到位就能访问到该元素,这个时间为K,时间复杂度用大O表示法标记为O(1),省略了K。而在数组中查找某元素,我们并不知道这个元素在数组的什么位置,假设数组的长度为n,有可能该元素刚好在数组的下标为0的位置(第一个位置)循环1次就匹配到了,时间复杂度为O(1)。也有可能在数组下标为n-1的位置(最后一个位置)我们要循环n次才能匹配到该值,时间复杂度为O(n),按照概率计算下来平均是n/2,即平均时间复杂度为O(n/2),但我们不应该只考虑平均值,我们要考虑最坏的情况,即假设每次匹配的元素都在数组的最后一位,因为最坏情况是一种运行时间保证,运行时间不会再长了,如果我们没特别指定,我们提到的运行时间都是最坏情况的运行时间,即在数组中查找某元素,时间复杂度为O(n);

在长度为n数组中:

直接通过下标去访问元素,时间复杂度为O(1)。

需要循环查找元素的时候,时间复杂度为O(n)。

下一章我们将分析ArrayList的删除元素的源码,来分析一下ArrayList的时间复杂度,进而了解ArrayList的优点与不足。

下一篇:待续注:本专栏文章首发于公众号:saysayJava。所有示例代码均已上传至公众号,需要请关注下载。

如果喜欢本系列文章,请为我点赞或顺手分享,您的支持是我继续下去的动力,您也可以在评论区留言想了解的内容,有机会本专栏会做讲解,最后别忘了关注一下我。

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_29181861/article/details/114249248

智能推荐

安装11202 RAC for solaris x86_64时碰到multicasting问题_普通网友的博客-程序员宅基地

在安装11.2.0.2RAC for Solaris x86_64环境是,节点2上运行root.sh碰到错误。详细错误信息为:OLR initializatio...

layui table.render后台传参问题_33三三的博客-程序员宅基地_table.render 参数

不知道大家有没有遇到这样的问题想在table.render传除了page 和 limit 的参数只需要在where 里面 加想传的字段就可以了layui.use('table', function(){ var userId = user.user[0].userId; var table = layui.table; table.render({ elem: '#test' ,url:'http://localhost:8181/salary/fin

android 接口 sql注入,light-dao框架升级(基于接口的sql注入)_weixin_39593593的博客-程序员宅基地

1 起因在这篇文章中:我们介绍了light-dao框架的基本实现。在使用了一段时间后我发现,这个框架在某些场景下,还是过重了。比如:select * from info where id = 10;如果使用light-dao中原本的做法,需要这样:@Select("select * from info where id = {0}")List selectUserInfo(int id);当然,在...

JAVA错误处理大集合_lw371496536的博客-程序员宅基地

0、 需要标识符a) 不在函数内1、 非法表达式开始b) 可能:丢失括号 .2. no data found a) 可能:setInt(1,100)中,没有100这个值3. 找不到符号a) 可能:没导入包4. 指定了无效URLa) 可能:数据库名或IP错误,即连接出错5. 类路径没有找到a) 可能: ClassNotFoundException: ora

计算机表格最高分,excel表格里怎样算最高分_ONE实验室的博客-程序员宅基地

在Excel中录入好数据以后进行数据统计,再统计过后多数需要算出最高值得,有些朋友可能不太会求最高值,接下来是学习啦小编为大家带来的excel如何求最高值的方法,欢迎大家来到学习啦学习。excel表格算最高分的方法1:下图是一个电子表格范例,我们要求全班同学在每个科目中的最高分2:鼠标选中如图中高等数学的最高分单元格,即B113:在B11单元格里面输入“=”号,电子表格的任务栏就会出现如图的变化,...

【Lintcode】1302. People Counting_记录算法的博客-程序员宅基地

题目地址:https://www.lintcode.com/problem/people-counting/description给定一个数组AAA,再给定一组询问,问每个数在AAA中出现了多少次。直接用哈希表计数。代码如下:import java.util.ArrayList;import java.util.HashMap;import java.util.List;import java.util.Map;public class Solution { /** *

随便推点

python的高级语法_笔记:Python高级语法汇总_斯提利科的博客-程序员宅基地

一:列表推导式num = [1, 4, -5, 10, -7, 2, 3, -1]filter_and_squared = []for number in num:if number > 0:filter_and_squared.append(number ** 2)print(filter_and_squared)filter_and_squared1 = [x ** 2 for x in...

android app怎么优化,Android-App性能优化_weixin_39556064的博客-程序员宅基地

上一篇我们讲了java的引用机制,今天我们来一下和它有关的app性能优化(其实也不是很大)。性能优化的目标在网上也看到过很多相关的文章,他们基本总结为:快,稳,省,小,描述的很准确.如下图 快如何让app在运行过程过不卡顿,运行流畅,速度快,也就是说如何解决卡顿呢?我们先看看那些因素影响卡顿?1. UI,包括ui的绘制,刷新等2. 启动,包括冷启动,热启动,温启动等3. 跳转,页面跳转,前后天切换...

【20190902】【校招笔试题】最少的操作次数_新浪_Satisfying的博客-程序员宅基地

问题输入一个数字字符串,由 ',' 分隔开,每次只能操作任意一个数字,并且只能进行加一操作,问:若要该字符串没有重复元素,至少操作几次。思路及代码# 我的思路:先将字符串转为整型列表,然后进行排序(从小到大),遍历逐个元素,若结果中没有该元素则加入;若结果中存在该元素且后一个元素-该元素>1,那么进行加一(再判断加一之后是否在B中,如果在B中那么不断加一,不在则直接加入结果中)...

【鸿蒙开发日常记录】TickTimer(计时器)_RenYangSJTU的博客-程序员宅基地_鸿蒙计时器

【鸿蒙开发日常记录】TickTimer(计时器)HarmonyOS关方Java API接口文档为英文, 本系列根据笔者开发需要将文档进行总结并翻译.HarmonyOS提供的**计时器(定时器)**组件, 提供了Java接口.组件简介:TickTimer是Text类的子类.TickTimer类提供了一个 从基准时间(base time)开始正计时 (Count up) 或倒计时 (Count down) 的计时器.内嵌类TickTimer.TickListener此内嵌类提供了一个接口函数 o

心动的本质是什么_风动,幡动,仁者心动,到底是什么在动_good2know的博客-程序员宅基地

说起禅宗公案,最有名的恐怕莫过于“风动幡动”了。禅宗六祖慧能受具足戒之前住在法性寺,有天晚上他偶然听见两位僧人正为到底是风动还是幡动争论不休,于是他朗声插了句话。此言一出,非但两位僧人若有所悟,连主持印空都颇感惊愕,乃亲自为他剃度,并拜其为师。那么目不识丁的慧能究竟说了些什么能令老和尚也大为折服的话呢?原来他说的是:“不是风动,也不是幡动,而是你们的心在动。”风和幡是外在的、虚幻的,人心才是超越时...

N皇后问题_weixin_57772345的博客-程序员宅基地

题目描述魔法世界历史上曾经出现过一个伟大的罗马共和时期,出于权力平衡的目的,当时的政治理论家波利比奥斯指出:“事涉每个人的权利,绝不应该让任何权力大到压过其他力量,使他人无法立足于平等条件与之抗辩的地步。”所以,即使关押修罗王和邪狼的监狱里的每个暗势力之间的关系十分紧张,但为了维持监狱的正常秩序,如非必要,他们会尽可能地避免直接接触。这类似著名的N皇后问题,即在N×N格的国际象棋上摆放N个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,请问有多少种摆法。图所示即是摆法的一种。

推荐文章

热门文章

相关标签