ArrayList 常数时间和线性时间访问

Question

我一直在学习Java SE 7的技巧。我读到了关于 ArrayList 的一条声明：

• 访问以恒定时间执行。
• 插入/删除以线性时间执行。

我想知道什么是常数和线性时间访问？

- Ahmet Karakaya

---

这是 Java SE 7，不是 J2SE 或 Java2SE。 - Peter Lawrey

Answer 1

常量时间意味着每个操作执行需要花费多少时间都有一个硬性限制。

线性时间指一个ArrayList包含越多对象（元素）操作所需的时间就越长。这种关系是线性的，即时间(操作) ≤ 常量 * 元素数量

在复杂度分析中，我们将其称为大O符号，线性时间表示为O(n)，常量时间表示为O(1)

---

原因是：

• 访问是普通的数组访问，在RAM机器上（例如我们的PC）中以常量时间完成。
• 插入/删除 - 如果不是最后一个元素，则需要移动所有后续元素：（插入需要向右移动，删除需要向左移动）- 因此实际上需要线性数量的操作来执行插入/删除（除非它是最后一个元素）。

- amit

Answer 2

意义如下：

• constant 意味着时间总是相同的，不管列表长度长短。

  [常数时间 在 大O符号 中也称为 O(1)]

• linear 意味着随着列表增长，所需时间会变长，但以线性方式增长，例如对包含 20 个元素的列表执行线性操作所需的时间比包含 10 个元素的列表多两倍。

  [线性时间 在 大O符号 中也称为 O(n)]

  精确说明：在比较算法时通常提供最坏情况下的性能，因此需要的时间小于或等于线性。

在您的情况下，列表的实现基于数组（因此名称为 ArrayList）如下所示：

访问时间是常数，因为当程序知道列表的第一个元素在哪里以及每个单元格的大小时，它可以使用简单的数学运算直接获取第 n 个元素，例如：

element_n_cell = element_1_cell + (cell_size * n)

插入和删除操作比其他操作更加耗时，原因如下：

1. 当你在某个位置插入或删除一个元素时，随后的所有元素都需要被移动。

2. 数组无法调整大小，因此当你创建一个新的ArrayList时，Java会创建一个预定义长度为s的数组，并且只要它适合，就会一直使用同一个数组。当你添加第(s+1)个元素时，程序需要创建一个更大的数组并将所有元素复制到新数组中。

- enrico.bacis

---

这不是线性时间的原因。虽然它只解释了最坏情况，但动态数组的平摊复杂度也是线性时间，因为在中间插入或删除元素需要将所有后续元素向右或向左移动。这使得它在平摊分析中也是O(n)，而不仅仅是最坏情况。 - amit

是的，你说得对！我在考虑添加:D，我会修复它！谢谢。 - enrico.bacis

Answer 3

了解常数时间访问

java.util.ArrayList 实现了 java.util.RandomAccess 接口，这是一个标记接口，表示您可以直接访问此集合的任何元素。这也意味着访问任何元素需要相同的时间（常数时间）。

如果我们使用 java.util.LinkedList，则访问最后一个元素比访问第一个元素需要更多的时间。

- Yuresh Karunanayake