java ArrayList 常量时间和线性时间访问
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/13288854/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
ArrayList Constant-time and Linear Time Access
提问by Ahmet Karakaya
I have been learning the tips of Java SE 7. I have read a statement about ArrayList:
我一直在学习 Java SE 7 的技巧。我已经阅读了关于ArrayList以下内容的声明：
- Accessis performed in constant time.
- Insertion/deletionis performed in linear time.
- 访问是在恒定时间内执行的。
- 插入/删除是在线性时间内执行的。
I would like to know what is constantand lineartime access?
我想知道什么是常数和线性时间访问？
回答by amit
constant time means there is a hard bound how much time each op will take to perform.
恒定时间意味着每个操作需要花费多少时间来执行是有硬限制的。
Linear time means the longer the ArrayListis (more object it contains) the longer time the op will take. The connection is linear, i.e. time(op) <= CONST * #elements
线性时间意味着时间越长ArrayList（包含的对象越多），操作所需的时间就越长。连接是线性的，即time(op) <= CONST * #elements
In complexity analysis, we refer it as big O notationand linear time is O(n), and constant time is O(1)
在复杂度分析中，我们将其称为大 O 表示法，线性时间为O(n)，常数时间为O(1)
The reason for it is:
原因是：
- Access is plain array access, and it is done in constant time in RAM machine (such as out PCs).
- Insertion/Deletion - if it is not in the last element, requires shifting all following elements: (Insertion requries shifting to the right, and deletion to the left) - thus you actually need a linear number of OPs to perform insertion/deletion (unless it is the last element)
- 访问是普通的数组访问，它是在 RAM 机器（例如外部 PC）中以恒定时间完成的。
- 插入/删除 - 如果它不在最后一个元素中，则需要移动以下所有元素：（插入需要向右移动，向左移动）-因此您实际上需要线性数量的 OP 来执行插入/删除（除非它是最后一个元素）
回答by enrico.bacis
The meanings are:
含义是：
constantmeans that the time is always the same, it doesn't matter the length of the List.
[constant timeis also called O(1)in Big-O notation]
linearmeans that the more the List grows, the longer is the time, but in a linear way, so for example to perform a linear operation on a list that contains 20 elements it will take two times the time needed for a list with 10 elements.
[linear timeis also called O(n)in Big-O notation]
A precisation: when comparing algorithms is normally provided the worst case performance, so it means that the time needed is less or equal than linear.
常量意味着时间总是相同的，与列表的长度无关。
[常数时间在Big-O 符号中也称为O(1)]
线性意味着 List 增长得越多，时间越长，但以线性方式，因此例如对包含 20 个元素的列表执行线性操作，它需要的时间是包含 10 个元素的列表所需时间的两倍.
[线性时间在Big-O 符号中也称为O(n)]
准确地说：当比较算法时，通常会提供最坏情况下的性能，因此这意味着所需的时间小于或等于线性。
In your case the implementation of the List is based on arrays (so the name ArrayList) like this:
在您的情况下， List 的实现基于数组（因此名称ArrayList），如下所示：
The access time is constant because when the program knows where the first element of the list is and how big is every cell, it can directly get the n-th element using simple math like:
访问时间是恒定的，因为当程序知道列表的第一个元素在哪里以及每个单元格有多大时，它可以使用简单的数学方法直接获取第n个元素，例如：
element_n_cell = element_1_cell + (cell_size * n)
Insertions and deletions are more time-expensive for two reasons:
插入和删除更耗时，原因有二：
When you insert or delete an element in a position, all the following elements need to be shifted.
An array can't be resized, so when you instantiate a new ArrayList, Java will create an array with a pre-defined length s, and it will use the same array as long as it fits. When you add the (s+1)-th element, the program needs to create a bigger array and copy all the elements in the new one.
当你在一个位置插入或删除一个元素时，后面的所有元素都需要移动。
数组无法调整大小，因此当您实例化一个新的 ArrayList 时，Java 将创建一个具有预定义长度s的数组，并且只要它适合，它就会使用相同的数组。添加第(s+1)个元素时，程序需要创建一个更大的数组并复制新数组中的所有元素。
