java ArrayList 的时间复杂度
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/2182597/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Time complexity for java ArrayList
提问by Hidayat
Is ArrayListan array or a list in java? what is the time complexity for the get operation, is it O(n)or O(1)?
ArrayListjava中是数组还是列表？什么是get操作的时间复杂度，是它O(n)还是O(1)？
采纳答案by jjnguy
An ArrayListin Java is a Listthat is backed by an array.
ArrayListJava 中的AnList是由array.
The get(index)method is a constant time, O(1), operation.
该get(index)方法是一个常数时间，O(1)， 操作。
The code straight out of the Java library for ArrayList.get(index):
直接从 Java 库中提取的代码用于ArrayList.get(index)：
public E get(int index) {
RangeCheck(index);
return (E) elementData[index];
}
Basically, it just returns a value straight out of the backing array. (RangeCheck(index)) is also constant time)
基本上，它只是直接从支持数组中返回一个值。( RangeCheck(index)) 也是常数时间)
回答by tangens
It's implementation is done with an array and the get operation is O(1).
它的实现是用一个数组完成的，get 操作是 O(1)。
javadoc says:
javadoc 说：
The size, isEmpty, get, set, iterator, and listIterator operations run in constant time. The add operation runs in amortized constant time, that is, adding n elements requires O(n) time. All of the other operations run in linear time (roughly speaking). The constant factor is low compared to that for the LinkedList implementation.
size、isEmpty、get、set、iterator 和 listIterator 操作在恒定时间内运行。add 操作在分摊常数 time 内运行，即添加 n 个元素需要 O(n) 时间。所有其他操作都在线性时间内运行（粗略地说）。与 LinkedList 实现相比，常量因子较低。
回答by Carl Smotricz
To be pedantic, it's a Listbacked by an array. And yes, the time complexity for get()is O(1).
迂腐，它是List由数组支持的。是的，时间复杂度get()是 O(1)。
回答by Kristopher Ives
As everyone has already pointed out, read operations are constant time - O(1) but write operations have the potential to run out of space in the backing array, re-allocation, and a copy - so that runs in O(n) time, as the doc says:
正如每个人已经指出的那样，读取操作的时间是恒定的 - O(1) 但写入操作有可能耗尽后备数组中的空间、重新分配和复制 - 因此在 O(n) 时间内运行，正如文档所说：
The size, isEmpty, get, set, iterator, and listIterator operations run in constant time. The add operation runs in amortized constant time, that is, adding n elements requires O(n) time.All of the other operations run in linear time (roughly speaking). The constant factor is low compared to that for the LinkedList implementation.
size、isEmpty、get、set、iterator 和 listIterator 操作在恒定时间内运行。add 操作在分摊常数时间内运行，即添加 n 个元素需要 O(n) 时间。所有其他操作都在线性时间内运行（粗略地说）。与 LinkedList 实现相比，常量因子较低。
In practice everything is O(1) after a few adds, since the backing array is doubled each time it's capacity is exhausted. So if the array starts at 16, gets full, it's reallocated to 32, then 64, 128, etc. so it scales okay, but GC can hit up during a big realloc.
实际上，在添加几次之后，一切都是 O(1)，因为每次其容量耗尽时，后备数组都会加倍。所以如果数组从 16 开始，变满了，它会被重新分配到 32，然后是 64、128 等等。所以它可以扩展，但是 GC 可能会在大的重新分配期间出现。
回答by prime
Just a Note.
只是一个注释。
The get(index)method is a constant time, O(1)
该get(index)方法是一个恒定的时间，O(1)
But that's the case if we know the index. If we try to get the index using indexOf(something), that will cost O(n)
但是如果我们知道索引就是这种情况。如果我们尝试使用 获取索引indexOf(something)，那将花费O(n)
回答by Balaji Boggaram Ramanarayan
The arraylist is basically an implementation of array. so the time complexity of the CRUD operations on it would be :
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.
