我在某处读到ArrayList的add()和remove()操作在"平摊常数"时间内运行。这到底是什么意思?
在add(item)的实现中，我可以看到它的ArrayList使用了一个数组缓冲区，它最多是列表大小的3/2，如果它已满，则调用System.arraycopy()，它应该在O(n)而不是O(1)时间内执行。那么，是不是那个系统。arraycopy尝试做一些比将元素一个接一个地复制到新创建的数组更聪明的事情，因为时间实际上是O(1)?
结论:add(item)在平摊常数时间内运行，但add(item, index)和remove(index)不运行，它们在线性时间内运行(如答案所述)。
我在某个地方读到ArrayList的add()和remove()操作在"平摊常数"时间内运行。
我不认为这对remove()是正确的，除非在特殊情况下。
-
对随机元素的
remove(Object)调用平均必须对列表中一半的条目调用equals，然后复制另一半的引用。 -
对随机元素的
remove(int)调用平均必须复制一半元素的引用。
remove(...)将平均为O(1)(例如平摊)的唯一情况是当您使用remove(int)从列表末尾删除元素时，
"摊销"大致表示"在整个运行时平均"。是的，数组复制将是O(n)。但这只会在列表已满时发生，这种情况发生1/n次。
我认为平摊常数时间只是意味着如果你做大量的操作，它的时间是常数。所以在一个测试中，有一百万个项目到列表中，然后在另一个测试中，向列表中添加二百万个项目。后者应该比前者慢约2倍，因此，平摊常数时间
平摊常数时间不同于常数时间
基本上平摊O(1)意味着在n个操作中，任何操作的平均运行时间为O(1)。
对于数组列表，其工作方式如下:
(O(1) insert + O(1) insert +…+ 0 (n) array copy)/n次操作= 0 (1)
线程中Amortized Constant的含义
摊余时间:
如果你做了一个操作，比如说一百万次，你并不真正关心这个操作的最坏情况或最好情况——你关心的是当你重复这个操作一百万次时总共花了多少时间。
因此，如果操作偶尔非常慢并不重要，只要"偶尔"是罕见的，以使缓慢被稀释掉。从本质上讲，平摊时间意味着"每次操作所花费的平均时间，如果你做很多操作的话"。摊销时间不一定是常数;你可以有线性和对数平摊时间或者其他任何东西
让我们以mats的动态数组为例，您可以反复向其中添加新项。通常，添加一个项目需要恒定的时间(即O(1))。但是每次数组满了，就分配两倍的空间，将数据复制到新区域，并释放旧空间。假设分配和释放在常量时间内运行，这个扩展过程需要O(n)时间，其中n是数组的当前大小。
所以每次放大，你花的时间是上次放大的两倍。但你也等了两倍的时间才去做!因此，每次扩展的成本可以在插入中"分摊"。这意味着从长远来看，向数组中添加m项所花费的总时间为O(m)，因此平摊时间(即每次插入时间)为O(1)。