算法 | Java中ArrayList扩容时时间复杂度是多少？

小鱼儿 2023-10-03 22:38 40阅读 0赞

### 前言 ###

本文主要介绍动态数组基本概念以及`ArrayList`扩容时间复杂度分析。

### 动态数组 ###

说起动态数组，我们首先来看下什么是静态数组？

静态数组就是初始化后，数组长度不会再变的数组。与之相反，动态数据的长度是可以变化的，当数组中存储数据时存不下时，他会自动进行扩容以能够存放更多的数据。

比如，现在有一个数组长度为4，当放入4个元素时，数组容量已经满了，当要放入第5个元素时，动态数组会先生成一个新的数组，长度为原来的2倍，然后把原数组的数据进行复制过去，再进行放入第5个元素，如果在接下来放入的过程中，容量又不够了，那么动态数组就会再把长度扩大一倍，以此类推。

看到这里，是不是想起了`Java`中的`ArrayList`？`ArrayList`底层也是数组，也会自动扩容，只不过`ArrayList`扩容时，会扩大到原来的`1.5`倍。

### 扩容时间复杂度 ###

那么就产生了一个问题，我们知道在数组中查询一个元素的位置的时间复杂度为O(1)，那么在`ArrayList`中查找一个元素时，如果已经扩容完了，那么查询一个元素的位置的时间复杂度也为O(1)。

但是，我们来看下`ArrayList`在扩容时的大致过程：

1.  原数组中容量满了。
2.  生成一个新的数组，长度为原来的1.5倍。
3.  把原数组中的元素复制到新的数组中。
4.  原数组销毁。

那么，这个`ArrayList`的扩容操作会不会影响`ArrayList`的整体表现呢？

扩容时间复杂度分析

先来分析下，在数组中加入N个元素时，扩容的总代价是多少？

为了方便分析，这里假设`ArrayList`扩容时，会扩大到原来的`2`倍计算，不会影响整体的时间复杂度。

先来看下`ArrayList`扩容时，最差的情况下，时间复杂度是多少。

最差的情况下`ArrayList`的长度为1，我要加入100个元素，分析下扩容的过程。

1.  加入1个元素时，不涉及扩容。
2.  加入2个元素时，需要扩容1次，扩容后数组长度为2，复制元素到新数组。
3.  加入3个元素时，需要扩容2次，扩容后数组长度为4，复制元素到新数组。
4.  加入5个元素时，需要扩容3次，扩容后数组长度为8，复制元素到新数组。
5.  ....

我们来看下，数组的长度变化为：`1 -> 2 -> 4 -> 8 -> 16 -> ... -> N`，可以看到这个变化过程为一个等比数列。

还记得等比数列的公共吗？

Sn = na1 \* 1−qn1−q\\frac\{1-q^n\}\{1-q\}1−q1−qn

在这里`n = logN`，`q = 2`， 可以得出最终结果为：

Sn = N - 1

因此时间复杂度为O(N)。

当扩容到`N`时，把时间复杂度均摊到每次一扩容操作上，也就是(N - 1)/N = 1 -1N \\frac\{1\}\{N\}N1，所以均摊后的时间复杂度为O(1)。同理，扩容后复制的平均复杂度也为O(1)，插入的平均复杂度也是O(1)，那么动态扩容时，一个元素插入的最大代价为3倍的O(1)，在计算时间复杂度时，常数以及系数是可以忽略不计的，所以最终的时间复杂度为O(1)。

### 总结 ###

本文主要介绍动态数组基本概念以及`ArrayList`扩容时间复杂度分析，经过上面的分析我们可以得出结论，`ArrayList`扩容操作时间复杂度为O(1)。

发表评论取消回复

表情：

评论列表（有 0 条评论，40人围观）

还没有评论，来说两句吧...

相关阅读

相关面试题：ArrayList扩容时扩容多少？

大家好，我是你们的小米！今天要和大家一起来探讨一个在Java面试中经常被问到的问题：“ArrayList扩容时扩容多少？”相信很多小伙伴都在面试中遇到过这个问题，那么接下来，我

今天药忘吃喽~/ 2024年03月23日 21:58/ 0 赞/ 136 阅读

相关【算法】时间复杂度，空间复杂度

文章目录一：时间频度 1.1 度量一个程序(算法)执行时间的两种方法 1.2 基本介绍 1.3 举例说明

骑猪看日落/ 2024年03月02日 10:11/ 0 赞/ 181 阅读

相关算法 | Java中ArrayList扩容时时间复杂度是多少？

前言本文主要介绍动态数组基本概念以及`ArrayList`扩容时间复杂度分析。动态数组说起动态数组，我们首先来看下什么是静态数组？静态数组就是初始化后，

小鱼儿/ 2023年10月03日 22:38/ 0 赞/ 41 阅读

相关 [时间复杂度]-排序算法的时间复杂度

我们经常可以看到这样的描述：软件=数据结构+算法，可见算法基础对于一个程序员的重要性。算法中，有两个基本概念：时间复杂度和空间复杂度。时间复杂度：描述算法执行消耗的时

今天药忘吃喽~/ 2023年09月24日 14:38/ 0 赞/ 198 阅读

相关关于时间复杂度&什么是时间复杂度

文章目录简介常见的Big-Oh 简介精确的考虑程序运行时间会使得寸步难行，而且毫无意义，所以可以用一种“概量”的概念来衡量运行时间，称之为“时间

末蓝、/ 2023年09月23日 21:46/ 0 赞/ 133 阅读

相关算法 | Java中ArrayList扩容时时间复杂度是多少？

前言本文主要介绍动态数组基本概念以及`ArrayList`扩容时间复杂度分析。动态数组说起动态数组，我们首先来看下什么是静态数组？静态数组就是初始化后，

女爷i/ 2023年09月23日 20:18/ 0 赞/ 153 阅读

相关算法 - 空间复杂度时间复杂度

[关于算法空间复杂度的问题][Link 1] ‘算法空间复杂度’，别以为这个东西多么高大上，我保证你看完这篇文章就能明白。最近在啃算法，发现非常有趣。在我学习的

Bertha 。/ 2022年04月08日 08:29/ 0 赞/ 501 阅读

相关 Java中ArrayList和LinkedList区别时间复杂度与空间复杂度

源文章：[https://www.cnblogs.com/zjss/p/5232048.html][https_www.cnblogs.com_zjss_p_5232048.h

落日映苍穹つ/ 2022年03月22日 12:48/ 0 赞/ 130 阅读

相关算法 - 时间复杂度

注：本文仅为笔记 [原文][Link 1] [极客时间 - 数据结构与算法之美 - 03 | 复杂度分析（上）：如何分析、统计算法的执行效率和资源消耗？][- _ - 03

小灰灰/ 2022年03月07日 12:40/ 0 赞/ 367 阅读

相关算法时间复杂度

时间复杂度就是通常我们简称的复杂度，Ｏ(f(n))表示。常见的算法时间复杂度由小到大依次为： Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n\2)＜

蔚落/ 2021年06月24日 15:57/ 0 赞/ 578 阅读