Java ArrayList 的时间复杂性

time-complexity java arraylist

2022-08-31 13:08:27

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

答案 1

Java 中的是一个由 .ArrayListListarray

该方法是常数时间、、运算。get(index)O(1)

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

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

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

答案 2

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

javadoc 说：

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