java 在 ArrayList 的开头添加元素的时间复杂度是多少？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/16777853/
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
What is the time complexity of adding an element at the beginning of an ArrayList?
提问by lakeskysea
Say I have a ArrayList with n element in this array, and I add an element at the beginning:
假设我在这个数组中有一个带有 n 个元素的 ArrayList，我在开头添加了一个元素：
myArrayList.add(0,'some value');
What will be the time complexity of this operation?
这个操作的时间复杂度是多少？
The Java Docdoesn't specify this.
在Java文档不指定。
Also
还
I just start learning Java, and I saw the sentence
刚开始学Java，看到一句话
An ArrayList in Java is a List that is backed by an array.
What does 'backed' here mean? Thank you!
这里的“支持”是什么意思？谢谢！
回答by gkamal
Adding an element to beginning of array is O(n) - it would require to shift all the existing elements by one position.
在数组的开头添加一个元素是 O(n) - 它需要将所有现有元素移动一个位置。
All elements in an array list are stored in a contiguous array. If you add more elements than the current size of the array - it will be grown automatically to accommodate the new element.
数组列表中的所有元素都存储在连续数组中。如果添加的元素多于数组的当前大小 - 它将自动增长以容纳新元素。
Addition to the end is O(1) amortized over multiple insertions.
除了最后是 O(1) 在多次插入中摊销。
回答by Louis Wasserman
ArrayList.add(0, element)takes linear time, but the constant is very low, because it can use the blazing fast System.arraycopy.
ArrayList.add(0, element)需要线性时间，但常数很低，因为它可以使用 blazing fast System.arraycopy。
回答by Clark Thomborson
The ArrayList documentation is indeed obscure on this point -- I looked at it in SE11 just now, and it's unchanged since the first release of the Collections Framework (in Java 1.2).
ArrayList 文档在这一点上确实很模糊——我刚刚在 SE11 中看过它，并且自 Collections Framework 的第一个版本（在 Java 1.2 中）以来它没有改变。
I believe the intent of the authors of the ArrayList documentation was to specify that, on any implementation of Java, the appending operation (i.e. the add(E e)method) must run in constant amortized time, and that the list insertion operation (i.e. the add(int index, E e)method) must run in O(n)time, where nis the size of the list.
我相信 ArrayList 文档作者的意图是指定，在 Java 的任何实现上，附加操作（即add(E e)方法）必须在固定的摊销时间内运行，并且列表插入操作（即add(int index, E e)方法）必须运行在O(n)时间上，n列表的大小在哪里。
回答by Roland
- Building the list from scratch and adding lots of elements to the beginning runs in quadratic time: O(n2).
- Adding all elements to the end of the list and then calling Collections.reverse(list)runs in linear time: O(n).
- 从头开始构建列表并将大量元素添加到开始运行的二次时间：O(n 2)。
- 将所有元素添加到列表的末尾，然后调用 Collections.reverse(list)以线性时间运行：O(n)。
