java ArrayList的时间复杂度

ArrayList是一个数组或java中的列表？ 获取操作的时间复杂度是O(n)还是O(1) ？

Answer 1

Java中的ArrayList是一个由array支持的List 。

get(index)方法是一个常量， O(1)操作。

直接从ArrayList.get(index)的Java库中获取代码：

 public E get(int index) { RangeCheck(index); return (E) elementData[index]; } 

基本上，它只是返回一个值直接从支持数组。 （ RangeCheck(index) ）也是恒定的时间）

Answer 2

它的实现是通过一个数组完成的，get操作是O（1）。

javadoc说：

大小，isEmpty，get，set，iterator和listIterator操作在一定的时间内运行。 add操作以分摊的恒定时间运行，即添加n个元素需要O（n）个时间。 所有其他的操作都在线性时间内运行（粗略地说）。 与LinkedList实现相比，常数因子较低。

Answer 3

正如大家已经指出的那样，读操作是恒定的 – O（1），但是写操作有可能会耗尽后备arrays中的空间，重新分配和拷贝 – 这样在O（n）时间，正如文件所说：

大小，isEmpty，get，set，iterator和listIterator操作在一定的时间内运行。 add操作以分摊的恒定时间运行，即添加n个元素需要O（n）个时间。 所有其他的操作都在线性时间内运行（粗略地说）。 与LinkedList实现相比，常数因子较低。

在实践中一切都是O（1）几个加法之后，因为每次容量耗尽时，支持数组都会加倍。 所以如果数组从16开始，就会变满，重新分配到32，然后是64,128等，所以它可以扩展，但是GC可以在一个大的重新分配期间重新启动。

Answer 4

为了迂回，它是一个由数组支持的List 。 是的， get()的时间复杂度是O（1）。