java - 在 ArrayList 开头添加元素的时间复杂度是多少？

Question

假设我在这个数组中有一个带有 n 个元素的 ArrayList，我在开头添加了一个元素：

myArrayList.add(0,'some value');

这个操作的时间复杂度是多少？

Java Doc没有指定这一点。

还

刚开始学Java，看到了那句话

An ArrayList in Java is a List that is backed by an array.

这里的“支持”是什么意思？谢谢！

Answer 1

将元素添加到数组的开头是 O(n) - 它需要将所有现有元素移动一个位置。

数组列表中的所有元素都存储在一个连续的数组中。如果您添加的元素多于数组的当前大小 - 它将自动增长以适应新元素。

添加到最后是 O(1) 在多次插入中摊销。

Answer 2

ArrayList.add(0, element)需要线性时间，但常数很低，因为它可以使用极快的速度System.arraycopy。

Answer 3

ArrayList 文档在这一点上确实晦涩难懂——我刚才在 SE11 中查看了它，并且自 Collections Framework 的第一个版本（Java 1.2 中）以来它没有改变。

我相信 ArrayList 文档的作者的意图是指定，在任何 Java 实现中，附加操作（即add(E e)方法）必须在恒定摊销时间内运行，并且列表插入操作（即add(int index, E e)方法）必须运行O(n)及时，n列表的大小在哪里。

Answer 4

• 从头开始构建列表并在开头添加大量元素以二次时间运行：O(n ² )。
• 将所有元素添加到列表的末尾，然后调用 Collections.reverse(list)以线性时间运行：O(n)。