ArrayList中恒时间和线性时间访问

Question

我一直在学习Java SE 7的提示我看了一份声明中关于ArrayList：

• 访问在固定时间执行。
• 插入/缺失在线性时间执行。

我想知道什么是不断和线性时间访问？

Answer 1

恒定时间意味着每个操作将花费多少时间来执行硬约束。

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

在复杂的分析，我们称它作为big O notation和线性时间为O(n)，提供固定时间为O(1)

---

它的原因是：

• 访问是普通的数组访问，并且它在RAM机器中（例如，在PC机中）在不变的时间内完成。
• 插入/删除 - 如果它不在最后一个元素中，需要移动所有下列元素:(插入请求向右移动，向左删除） - 因此实际上需要线性数量的OP来执行插入/删除（除非它是最后一个元素）

Answer 2

含义是：

• 恒定意味着时间总是相同的，它并不重要的列表的长度。

  [恒定时间也被称为O（1）在Big-O notation]

• 线性意味着越列表的增长，较长是时间，但以线性方式，所以例如，要在包含20个元素的列表上执行线性操作，则需要两次包含10个元素的列表所需的时间。

  [线性时间也被称为为O（n）在Big-O notation]

  甲precisation：比较算法时通常提供的最坏情况性能，所以这意味着所需的时间少或等于线性。

在你的情况列表的实现是基于阵列（这样的名字的ArrayList）是这样的：

的访问时间是因为当程序知道在哪里不变列表的第一个元素是，每个单元格有多大，它可以使用简单的数学运算式直接得到：

element_n_cell = element_1_cell + (cell_size * n) 

个

插入和删除更多的时间，昂贵的原因有两个：

1. 当您插入或在一个位置删除元素，所有的以下内容需要转移。

2. 数组不能改变大小，所以当你实例化一个新的ArrayList，Java将创建一个数组与预先定义的长度小号，只要它符合它会使用相同的阵列。当你添加（s + 1） -th元素时，程序需要创建一个更大的数组并复制新数组中的所有元素。