ArrayList
在 Java 中是一个列表(list),但底层实现是数组(array)。对于 get 操作的时间复杂度是 O(1)
。
ArrayList
在 Java 中是一个列表(list),但底层实现是数组(array)。对于 get 操作的时间复杂度是 O(1)
。
ArrayList
是由array
支持的List
。
get(index)
方法是一个常数时间复杂度为O(1)
的操作。
ArrayList.get(index)
的代码直接来自于Java库:public E get(int index) {
RangeCheck(index);
return (E) elementData[index];
}
基本上,它只是直接从后备数组中返回一个值。 (RangeCheck(index)
) 也是常数时间。它的实现是通过一个数组来完成的,并且get操作的时间复杂度为O(1)。
javadoc说:
size、isEmpty、get、set、iterator和listIterator操作的运行时间都为常数时间。add操作的运行时间是均摊常数时间,也就是添加n个元素需要O(n)的时间。所有其他操作的运行时间都是线性时间(粗略地说)。与LinkedList实现相比,常数因子较低。
众所周知,读操作的复杂度是常数时间 - O(1),但写操作可能会在后备数组中空间不足、重新分配和复制时耗费O(n)的时间,正如文档所述:
大小、isEmpty、get、set、迭代器和listIterator操作都以恒定的时间运行。add操作以平摊常数时间运行,即添加n个元素需要O(n)的时间。所有其他操作都以线性时间运行(粗略地说)。与LinkedList实现相比,常数因子较低。
在实践中,仅需添加几个元素,一切都是O(1),因为每当后备数组达到容量极限时,它就会加倍。因此,如果数组从16开始,满了,就会被重新分配到32、64、128等,所以它的扩展性还可以。但在大的重新分配期间,垃圾回收可能会出现问题。
严格来说,它是由数组支持的List
。而且,get()
的时间复杂度确实为O(1)。
小提示。
get(index)
方法的时间复杂度是常数级别的,O(1)
但前提是我们已知道索引。如果我们尝试使用 indexOf(something)
来获取索引,那么时间复杂度将会是 O(n)
get/read : O(1) since you can seek the address directly from base
remove/delete : O(n) why ? Because once we delete the element at index, then we need to move the after values one by one to the left.
add : O(1) becuase you always add the end of the array - next free address available.
update : O(1) since you are just changing the value but nothing value moving....across the array.