ArrayList add(Type value) 方法如何 O(1) 摊销时间复杂度？

Question

ArrayList 的大多数实现在内部使用数组，当向列表添加元素时大小已经用尽时，它会通过执行以下操作来调整大小或“增长”：

所提供的解释是，增加列表对于您的平均添加操作来说是很少需要的，因此平均添加的时间复杂度为 O(1)，因此摊销常数时间。

我不明白这是怎么回事。假设列表增长 Q。简单的算术系列会告诉你，如果我要将 x 个元素添加到 ArrayList，内部完成的元素复制总数是 x^2 + Qx / 2Q，如果 x 比 [=] 大几倍21=].

当然，对于添加的前几个值，时间很可能是恒定的，但是对于添加足够多的元素，我们看到 平均时间复杂度对于每个加法运算都是线性的或 O(n)。因此，向列表中添加大量元素需要指数时间。我不明白单个添加操作的摊销时间复杂度是如何保持不变的。有什么我想念的吗？

编辑：我没有意识到列表增长实际上是几何增长的，这优化了摊销时间复杂度。

结论：

动态列表线性增长

让N = kQ

对于 N + 1 个插入

份数：

  Q + 2Q + 3Q + … + kQ
= (k / 2)(2Q + (k - 1)Q)
= (k / 2)(Q + kQ) 
= (kQ + k^2 * Q) / 2 
-> kQ + k^2 * Q

元素初始化：

  Q + 2Q + 3Q + 4Q + … + (k + 1) * Q 
= ((k + 1) / 2)(2Q + kQ) 
= (k^2 * Q + 2kQ + 2Q + kQ) / 2 
-> k^2 * Q + 3kQ + 2Q

廉价插入：

  kQ + 1 
-> kQ

总费用：2Q * k^2 + 5kQ + 2Q

每次插入的摊销成本：

  2k + 5 + 2 / k 
-> 2k + 2 / k
-> O(N / Q)
-> O(N)

动态列表几何增长

让N = Q^k

对于 N + 1 个插入

份数：

  1 + Q + Q^2 + … +  Q^k 
= (1 - Q^(k + 1)) / (1 - Q) 
-> Q^k

元素初始化：

  1 + Q + Q^2 + … + Q^(k + 1) 
= (1 - Q^(k + 2)) / (1 - Q) 
-> Q^(k + 1)

廉价插入：

  Q^k + 1 
-> Q^k

总费用：2Q^k + Q^(k + 1)

每次插入的摊销成本：

  2 + Q
-> O(1)

比较

数组的几何resizing/growth是常量时间，线性缩放是线性时间。比较这两种增长方式，看看性能差异以及为什么选择 ArrayLists 几何增长是很有趣的。

Answer 1

不失一般性，假设链表的初始容量为1。进一步假设每次插入超过容量时，容量翻倍。现在考虑插入 2^k + 1 个元素（这通常是最坏的情况，因为最后一个操作触发了动态增长）。

有k个触发动态增长的插入，其累计成本为

1 + 2 + 4 + 8 + ... + 2^k = 2^(k+1) - 1

其他“廉价”插入的累计成本是 2^k - k + 1。

但是我们对 摊销的 复杂度感兴趣，因此我们必须对所有 2^k + 1 操作进行平均：

  (2^(k+1) + 2^k - k) / (2^k + 1)
< (2^(k+1) + 2^k - k) / 2^k
= 2 + 1 - k/2^k
= O(1)

因此，向列表中插入 2^(k+1) 个元素的分摊时间复杂度为 O(1) 每次插入，并且常数因子接近 3。将任何其他数量的元素插入到列表中不会更糟，因此每次插入的分摊时间复杂度通常为 O(1)。

How is the ArrayList add(Type value) method O(1) amortized time complexity?