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) 时间。

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

希望这对您有所帮助!