java ArrayList 的时间复杂度

Question

ArrayList

在java中是数组还是列表？ get 操作的时间复杂度是多少，是

O(n)

还是

O(1)

？

Answer 1

Java 中的

ArrayList

是由

List

支持的

array

。

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

数组列表基本上是数组的实现。所以对其进行 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.

Answer 7

通过 ArrayList 中的索引检索元素的时间复杂度为 O(1)，即常数时间。

以下是详细解释：

连续内存分配：

• ArrayList 使用底层数组数据结构。该数组将元素存储在连续的内存位置中。
• 此特性允许使用索引直接访问。

恒定时间访问：

• 给定元素的索引（位置），计算其内存地址涉及到数组基地址的简单偏移量。
• 此计算与数组的大小无关，因此时间复杂度恒定。

类比：

• 想象一本有页码的书。要访问特定页面（索引），您可以直接翻到该页码，无需扫描整本书（线性搜索）。

补充要点：

• 虽然通过索引检索元素很有效，但修改 ArrayList（添加/删除元素）有时会产生成本。
• 在最坏的情况下（例如，在开头添加元素），ArrayList 可能需要调整其内部数组的大小以容纳新元素。此调整大小操作可能需要与数组大小相关的线性时间 (O(n))。

总的来说，理解连续内存分配的概念对于掌握 ArrayList 中的高效检索操作至关重要。

注：-

当然！让我们用一个简单的例子来说明这一点。

假设我们有一个名为colors的ArrayList，包含以下元素：

colors = ["Red", "Green", "Blue", "Yellow", "Orange"]

在内存中，这些元素可能会像这样连续存储：

Memory Address | Value
---------------|------
1000           | "Red"
1004           | "Green"
1008           | "Blue"
1012           | "Yellow"
1016           | "Orange"

现在，假设我们要访问索引 2 处的元素，即“蓝色”。

为了找到“Blue”的内存位置，ArrayList 将使用一个简单的计算：

1. 它从 ArrayList 的内存基地址开始（假设它是 1000）。
2. 它根据我们要访问的索引向该基地址添加偏移量。由于我们想要索引 2 处的元素，因此偏移量将为 2 * size_of_element （为了简单起见，我们假设它是 4 个字节），因此偏移量将为 2 * 4 = 8。
3. 它将这个偏移量添加到基地址：1000（基地址）+ 8（偏移量）= 1008。
4. 然后直接访问内存位置 1008 以检索元素“Blue”。

这个计算很简单，并且不依赖于ArrayList的大小。因此，在 ArrayList 中通过索引访问元素的时间复杂度是 O(1)。