ArrayList部分一共五篇文章了，并且引入了时间复杂度来分析， 强烈建议大家一定要按顺序阅读 ，相关文章分别是：

1、

2、

3、时间复杂度 – Java那些事儿

4、三顾ArrayList – Java那些事儿

5、ArrayList的时间复杂度 – Java那些事儿

最近看了一下评论区里，大家都急着想要了解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的优点与不足。

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

上一篇：