75

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

4

6 回答 6

126

ArrayListJava 中的anList是由array.

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

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

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

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

于 2010-02-02T08:10:42.957 回答
23

它的实现是用一个数组完成的，get 操作是 O(1)。

javadoc 说：

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

于 2010-02-02T08:09:11.353 回答
12

正如每个人已经指出的那样，读取操作是恒定时间 - O(1) 但写入操作有可能耗尽后备数组中的空间、重新分配和复制 - 因此在 O(n) 时间内运行，正如文档所说：

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

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

于 2010-02-02T08:18:53.637 回答
5

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

于 2010-02-02T08:10:31.660 回答
1

只是一个注释。

该get(index)方法是一个恒定的时间，O(1)

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

于 2018-02-02T09:23:35.537 回答
0

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.
于 2020-05-15T23:25:20.420 回答