java时间复杂度计算_时间复杂度 - Java那些事儿专栏_江平舟的博客-程序员宅基地
技术标签： java时间复杂度计算
ArrayList部分一共五篇文章了，并且引入了时间复杂度来分析，强烈建议大家一定要按顺序阅读，本文是第3篇，前两篇文章分别是：
最近看了一下评论区里，大家都急着想要了解HashMap，先不要着急，要完整的了解HashMap的内部实现，我们还需要一些基础知识，有了这些基础知识，我们才能更好的理解HashMap，其实我们已经在不知不觉进入了数据结构的大门，为了以后让大家能更好的理解后续文章，本文我们先引入时间复杂度这个概念。
还是那个Person对象，增加了一个属性年龄
创建一个数组，并在数组里放了10个Person对象，老规矩，我们上图：
假如我们有这么一个需求，我们想知道小组里周八的年龄，相信大家都会写代码去找：
需要循环取6次从数组里获取Person对象。
这时候小明同学过来说，哎呀，我知道周八在小组的第5个位置(数组下标5)，不用循环，我们直接找他就是
不需要循环，1次就取到了Person对象：
无论数组中有多少个元素，每次去读取元素和并比较的时间总是相同的，假设这个时间为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。所有示例代码均已上传至公众号，需要请关注下载。
如果喜欢本系列文章，请为我点赞或顺手分享，您的支持是我继续下去的动力，您也可以在评论区留言想了解的内容，有机会本专栏会做讲解，最后别忘了关注一下我。
智能推荐
安装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个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，请问有多少种摆法。图所示即是摆法的一种。