algorithm - 当维基百科说在动态数组末尾插入项目的复杂性是 O(1) 摊销时，它是什么意思？

Question

http://en.wikipedia.org/wiki/Dynamic_array#Performance

它到底是什么意思？

我认为在最后插入将是 O(n)，因为您必须分配原始数组空间的两倍，然后将所有项目移动到该位置并最后插入项目。这个 O(1) 怎么样？

Answer 1

摊销的 O(1) 效率意味着 n 次插入的运行时间总和将为 O(n)，即使任何单个操作可能需要更长的时间。

由于复制所有内容所需的工作，附加元素可能需要 O(n) 时间，这是绝对正确的。但是，由于数组每次扩展时都会加倍，因此昂贵的加倍步骤发生的频率越来越少。结果，在 n 次插入中完成的总工作是 O(n) 而不是 O(n ² )。

详细说明：假设您要插入总共 n 个元素。调整矢量大小时复制元素的总工作量最多为

1 + 2 + 4 + 8 + ... + n ≤ 2n - 1

这是因为首先复制一个元素，然后复制两倍，然后复制两倍，等等，在绝对最坏的情况下复制所有 n 个元素。这个几何级数的总和为 2n - 1，因此在所有复制步骤中最多移动 O(n) 个元素。由于您进行了 n 次插入，并且在所有这些操作中只进行了 O(n) 总工作复制，因此每次操作的摊销效率为 O(1)。这并不是说每个操作都需要 O(1) 时间，而是说 n 个操作总共需要 O(n) 时间。

对于这背后的图形直觉，以及将数组加倍而不是仅仅增加少量的基本原理，您可能需要查看这些演讲幻灯片。最后的图片可能非常相关。

希望这可以帮助！

Answer 2

是的，每个单独的重新分配都是 O(N)。但是在接下来的 N 次插入中，您无需执行任何操作。所以每次插入的“平均”成本是 O(1)。我们说“成本在多个操作中摊销”。