假设我在这个数组中有一个带有 n 个元素的 ArrayList,我在开头添加了一个元素:
myArrayList.add(0,'some value');
这个操作的时间复杂度是多少?
Java Doc没有指定这一点。
还
刚开始学Java,看到了那句话
An ArrayList in Java is a List that is backed by an array.
这里的“支持”是什么意思?谢谢!
将元素添加到数组的开头是 O(n) - 它需要将所有现有元素移动一个位置。
数组列表中的所有元素都存储在一个连续的数组中。如果您添加的元素多于数组的当前大小 - 它将自动增长以适应新元素。
添加到最后是 O(1) 在多次插入中摊销。
ArrayList.add(0, element)
需要线性时间,但常数很低,因为它可以使用极快的速度System.arraycopy
。
ArrayList 文档在这一点上确实晦涩难懂——我刚才在 SE11 中查看了它,并且自 Collections Framework 的第一个版本(Java 1.2 中)以来它没有改变。
我相信 ArrayList 文档的作者的意图是指定,在任何 Java 实现中,附加操作(即add(E e)
方法)必须在恒定摊销时间内运行,并且列表插入操作(即add(int index, E e)
方法)必须运行O(n)
及时,n
列表的大小在哪里。