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

开启掘金成长之旅！这是我参与「掘金日新计划 · 12 月更文挑战」的第31天，点击查看活动详情

前言

本文主要介绍动态数组基本概念以及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)。