5

我一直在学习 Java SE 7 的技巧。我已经阅读了有关以下内容的声明ArrayList：

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

我想知道什么是恒定和线性时间访问？

4

3 回答 3

11

恒定时间意味着每个操作执行所需的时间有一个硬性限制。

线性时间意味着ArrayListis 越长（它包含的对象越多）操作所需的时间就越长。连接是线性的，即time(op) <= CONST * #elements

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

其原因是：

  • 访问是普通数组访问，它是在 RAM 机器中以恒定时间完成的（例如出 PC）。
  • 插入/删除 - 如果它不在最后一个元素中，则需要移动以下所有元素：（插入需要向右移动，向左移动） - 因此您实际上需要线性数量的 OP 来执行插入/删除（除非它是最后一个元素）
于 2012-11-08T12:12:25.517 回答
10

含义是：

  • 常数意味着时间总是相同的，与列表的长度无关。

    [常数时间在Big-O 表示法中也称为O(1) ]

  • 线性意味着 List 增长得越多，时间就越长，但是以线性方式，例如，要对包含 20 个元素的列表执行线性操作，它将花费 10 个元素的列表所需时间的两倍.

    [线性时间在Big-O 表示法中也称为O(n) ]

    A precisation：在比较算法时通常提供最坏情况下的性能，因此这意味着所需的时间小于或等于线性。

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

Java ArrayList 解释

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

element_n_cell = element_1_cell + (cell_size * n)

插入和删除更耗时，原因有两个：

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

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

于 2012-11-08T12:13:21.913 回答
0

不明白恒定时间访问

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

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

于 2021-06-19T10:19:36.167 回答