Java ArrayList的时间复杂度

Question

ArrayList 在 Java 中是一个列表（list），但底层实现是数组（array）。对于 get 操作的时间复杂度是 O(1)。

- Hidayat

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)) 也是常数时间。

- jjnguy

---

由于array[n]意味着系统将仅执行一个数学计算=offsetvalue +（变量的大小）*n，因此它是恒定时间。整个计算过程将在处理器中完成，而不需要一遍又一遍地访问内存位置。这就是为什么它是O（1）的原因。 - Anil Sharma

Answer 2

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

javadoc说：

size、isEmpty、get、set、iterator和listIterator操作的运行时间都为常数时间。add操作的运行时间是均摊常数时间，也就是添加n个元素需要O(n)的时间。所有其他操作的运行时间都是线性时间（粗略地说）。与LinkedList实现相比，常数因子较低。

- tangens

Answer 3

众所周知，读操作的复杂度是常数时间 - O(1)，但写操作可能会在后备数组中空间不足、重新分配和复制时耗费O(n)的时间，正如文档所述：

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

在实践中，仅需添加几个元素，一切都是O(1)，因为每当后备数组达到容量极限时，它就会加倍。因此，如果数组从16开始，满了，就会被重新分配到32、64、128等，所以它的扩展性还可以。但在大的重新分配期间，垃圾回收可能会出现问题。

- Kristopher Ives

---

有点跑题，但我不希望有人被搞糊涂，没有真正注意到获取操作的重点。 - Kristopher Ives

对于第一句话有所争议，因为它似乎暗示写入操作的运行时间是O(n)。但这不是文档中所说的，文档说添加n个元素需要O(n)。对于单个元素，插入时间仍然是O(1)。重新分配、复制等只是使其变成了一个稍微“更大”的O(1)。 - Carl Smotricz

嗨，Carl Smotricz，如何理解重新分配是“有点"更大"的O(1)"？例如，如果您有一个大小为16的数组。如果您尝试添加第17个元素，则所有16个先前的元素都需要复制到新数组中，这是O(n)，与O(1)相比差别很大... - Akh

@AKh，是的，这就是为什么它说是摊销常数时间。大多数插入操作的时间复杂度将为O(1)，但偶尔会出现O(n)的情况。总体而言，插入操作的时间复杂度表现为O(1)。 - Mikael Ohlson

@AJMansfield 调整大小的时间是被考虑在内的，但您的近似是悲观的。当添加n个元素时，您执行了n次实际插入，并进行了log(n)次数组分配/复制。但是这些分配并不会花费n的成本，而是分别为2、4、8、16、32等。如果插入一个元素的成本为A，而分配+复制内存的成本为B * k，其中k是已分配数组的大小，则最终成本为A * n + B + 2B + 4B + 8B + ... + 2nB（在最坏情况下）<=（A + 4B）* n，即线性。 - Boris Dalstein

Answer 4

严格来说，它是由数组支持的List。而且，get()的时间复杂度确实为O(1)。

- Carl Smotricz

Answer 5

小提示。

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

但前提是我们已知道索引。如果我们尝试使用 indexOf(something) 来获取索引，那么时间复杂度将会是 O(n)

- prime

---

获取某个元素的indexOf无论如何都是O(n)。 - Reyansh Kharga

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.

- Balaji Boggaram Ramanarayan