java - ArrayList.add 方法的时间复杂度是多少？

<分区>

java documentation对于 class ArrayList<E>指定:

The size, isEmpty, get, set, iterator, and listIterator operations run in constant time. The add operation runs in amortized constant time, that is, adding n elements requires O(n) time. All of the other operations run in linear time (roughly speaking). The constant factor is low compared to that for the LinkedList implementation.

Each ArrayList instance has a capacity. The capacity is the size of the array used to store the elements in the list. It is always at least as large as the list size. As elements are added to an ArrayList, its capacity grows automatically. The details of the growth policy are not specified beyond the fact that adding an element has constant amortized time cost.

这怎么可能？

方法void add(int index, E element)在此列表中的指定位置插入指定元素，将所有后续元素向右移动。虽然在 ArrayList 的末尾插入 n 元素似乎可以实现 摊销常数时间通过使用几何增长重新分配支持数组，这将不允许在数组中间插入元素时摊销常数时间。

文档是否仅涉及 add(element E)方法还是有一个巧妙的技巧可以在所有情况下实现摊销常数时间？

最佳答案

如 this answer 中所述, Oracle 使用了一个令人困惑的约定:当他们提到 add 方法时，他们通常指的是 add(E element) 方法，而 void add (int index, E element) 被称为 insert 方法...方法名确实令人困惑，类名也是如此。

关于java - ArrayList.add 方法的时间复杂度是多少？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/62882681/

上一篇：azure - 动态地将环境变量传递到Azure容器实例

下一篇：apache-spark - Dataproc 未从自定义 Conda channel 安装自定义 Conda 包

相关文章：

javascript - 什么会跑得更快？

python - 索引非常大的 Pandas 数据帧的最快方法

performance - 在命令窗口中使用编辑器时 Matlab 性能奇怪

java - 无法在 Android 中的 URL 中发送阿拉伯字符

java - 删除示例包仍然出现编译错误

java - Java 中创建数组和数组列表是一回事吗？

java - 将存储的数组值复制到数组列表JAVA中

java - 实现具有两个不同方法签名和主体的接口(interface)

java - 在我的 pojo 字段中使用 "public"修饰符而不是 "private"是否有任何风险？

java - 仅限整数？