java ArrayList的时间复杂度

Question

是ArrayListjava中的数组还是列表？get操作的时间复杂度是什么,是O(n)或者O(1)？

Answer 1

一个ArrayList在Java是一种List由一个支持array.

该get(index)方法是一个恒定的时间O(1),操作.

代码直接来自Java库ArrayList.get(index):

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

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

Answer 2

它的实现是通过数组完成的,get操作是O(1).

javadoc说:

size,isEmpty,get,set,iterator和listIterator操作以恒定时间运行.添加操作以分摊的常量时间运行,即添加n个元素需要O(n)时间.所有其他操作都以线性时间运行(粗略地说).与LinkedList实现相比,常数因子较低.

Answer 3

正如大家已经指出的那样,读操作是恒定时间--O(1)但是写操作有可能在后备阵列中耗尽空间,重新分配和复制 - 因此在O(n)时间内运行,正如文件所说:

size,isEmpty,get,set,iterator和listIterator操作以恒定时间运行.添加操作以分摊的常量时间运行,即添加n个元素需要O(n)时间. 所有其他操作都以线性时间运行(粗略地说).与LinkedList实现相比,常数因子较低.

实际上,经过几次添加后,所有内容都是O(1),因为每次容量耗尽时,后备阵列都会加倍.因此,如果数组从16开始,变满,它将被重新分配到32,然后是64,128等,所以它可以正常扩展,但GC可以在重新分配期间启动.

Answer 4

迂腐，它是List由数组支持的。是的，时间复杂度get()是 O(1)。