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

Question

我一直在学习Java SE 7的技巧.我读过一条声明ArrayList:

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

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

Answer 1

恒定时间意味着每个操作执行需要花费多少时间.

线性时间意味着时间越长ArrayList(它包含的对象越多)操作时间越长.连接是线性的,即time(op) <= CONST * #elements

在复杂性分析中,我们将其称为大O符号,线性时间是O(n),并且常数时间是O(1)

原因是:

• 访问是普通的阵列访问,它在RAM机器(例如外出PC)中持续进行.
• 插入/删除 - 如果它不在最后一个元素中,则需要移动所有后续元素:(插入请求向右移动,删除到左侧) - 因此您实际上需要线性数量的OP来执行插入/删除(除非它是最后一个元素)

Answer 2

含义是:

• 常量意味着时间总是相同的,与List的长度无关.

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

• 线性意味着List越长,时间越长,但是以线性方式,例如对包含20个元素的列表执行线性操作,将需要两倍于具有10个元素的列表所需的时间.

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

  精确化:当比较算法通常提供最差情况下的性能时,这意味着所需的时间小于或等于线性.

在你的情况下,List的实现基于数组(所以名称ArrayList),如下所示:

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

element_n_cell = element_1_cell + (cell_size * n)

由于两个原因,插入和删除更加耗时:

1. 在位置中插入或删除元素时,需要移动以下所有元素.

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