java ArrayList 的时间复杂度

Question

java中的ArrayList是数组还是列表？ get 操作的时间复杂度是多少，是 O(n) 还是 O(1)？

Answer 1

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

get(index) 方法是一个常数时间、O(1) 的操作。

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

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

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

Answer 2

它的实现是通过数组完成的，并且获取操作的时间复杂度为 O(1)。

javadoc 说：

大小、isEmpty、获取、设置、
iterator 和 listIterator 操作以常量运行
时间。加法操作在摊销常数时间内运行，
也就是说，添加n个元素需要O(n)时间。所有其他操作
以线性时间运行（粗略地说）。相比之下，常数因子较低
到 LinkedList 实现。

Answer 3

正如每个人都已经指出的那样，读取操作的时间复杂度为常数 - O(1)，但写入操作有可能耗尽后备数组、重新分配和复制中的空间 - 因此运行时间为 O(n) ，正如医生所说：

大小、isEmpty、get、set、迭代器、
和 listIterator 操作运行在
恒定时间。 添加操作运行
在摊余常数时间内，即
添加 n 个元素需要 O(n) 时间。
所有其他操作都运行在
线性时间（粗略地说）。这
与以下相比，常数因子较低
对于 LinkedList 来说
实施。

实际上，经过几次添加后，一切都是 O(1)，因为每次其容量耗尽时，后备数组都会加倍。因此，如果数组从 16 开始，满了，它会被重新分配到 32，然后是 64、128，等等。所以它可以扩展，但 GC 可能会在大的重新分配期间发生。

Answer 4

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

Answer 5

只是一个注释。

get(index) 方法的时间复杂度为常数，O(1)

但如果我们知道索引，情况就是如此。如果我们尝试使用 indexOf(something) 获取索引，这将花费 O(n)

Answer 6

arraylist 基本上是数组的实现。所以对其进行 CRUD 操作的时间复杂度为：

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.