我在某处读到 ArrayList 的 add() 和 remove() 操作在“摊销常数”时间内运行。这到底是什么意思？
在 add(item) 的实现中，我可以看到它 ArrayList 使用了一个数组缓冲区，它最多是列表大小的 3/2，如果它已满，< em>System.arraycopy() 被调用，它应该在 O(n) 内执行，而不是 O(1) 时间。那么 System.arraycopy 是否尝试做一些比将元素一个一个地复制到新创建的数组中更聪明的事情，因为时间实际上是 O(1)？
结论:add(item) 在分摊常数时间内运行，但 add(item, index) 和 remove(index) 不t，它们以线性时间运行(如答案中所述)。
最佳答案
I have read somewhere that ArrayList's add() and remove() operations run in "amortized constant" time.
我认为 remove() 不是这样，除非在异常情况下。
对随机元素的
remove(Object)调用平均必须对列表中的一半条目调用equals，然后复制引用另一半。对随机元素的
remove(int)调用平均必须复制一半元素的引用。
remove(...) 平均O(1) 的唯一情况(例如摊销)是当您使用 remove (int) 从列表末尾删除一些常量偏移量的元素。
关于Java:ArrayList add() 和 remove() 性能、实现？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/7910283/