维基百科表示在动态数组末尾插入一个项目的复杂性是O（1）摊销？ [英] What does Wikipedia mean when it says the complexity of inserting an item at the end of a dynamic array is O(1) amortized?

问题描述

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

究竟是什么意思？

我以为插入最后会是O（n），因为你'必须分配一个原始数组的两倍空间，然后将所有项移动到该位置，最后插入该项。这个O（1）如何？

I thought inserting at the end would be O(n), as you'd have to allocate say, twice the space of the original array, and then move all the items to that location and finally insert the item. How is this O(1)?

推荐答案

分摊O（1）效率意味着n个插入的运行时间的总和将即使O（n），即使任何个别操作可能需要更长时间。

Amortized O(1) efficiency means that the sum of the runtimes of n insertions will be O(n), even if any individual operation may take a lot longer.

您是绝对正确的，因为添加元素可能需要O（n）次工作需要复制一切。然而，由于阵列每次扩展时都增加了一倍，所以昂贵的倍增步骤指数下降越来越少。因此，在n个插入中完成的工作总结为O（n）而不是O（n ² ）。

You are absolutely correct that appending an element can take O(n) time because of the work required to copy everything over. However, because the array is doubled each time it is expanded, expensive doubling steps happen exponentially less and less frequently. As a result, the total work done in n inserts comes out to be O(n) rather than O(n²).

详细说明：假设您要插入总共n个元素。在调整向量大小时复制元素的总量将至多为

To elaborate: suppose you want to insert a total of n elements. The total amount of work done copying elements when resizing the vector will be at most

1 + 2 + 4 + 8 + ... + n&le 2n - 1

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

这是因为首先你复制一个元素，然后是两次，然后是两次，等等，在绝对最坏情况下复制所有n个元素。这个几何系列的总和适用于2n - 1，所以最多O（n）个元素在所有复制步骤中移动。由于您进行n个插入，并且只有O（n）个全部工作复制，每个操作的摊销效率为O（1）。这不表示每个操作需要O（1）次，但是n个操作需要O（n）个时间。

This is because first you copy one element, then twice that, then twice that, etc., and in the absolute worst case copy over all n elements. The sum of this geometric series works out to 2n - 1, so at most O(n) elements get moved across all copy steps. Since you do n inserts and only O(n) total work copying across all of them, the amortized efficiency is O(1) per operation. This doesn't say each operation takes O(1) time, but that n operations takes O(n) time total.

对于这样的图形直觉，以及作为将数组加倍的原理，只需增加一小部分，您可能需要查看这些演讲稿。朝向最后的图片可能非常相关。

For a graphical intuition behind this, as well as a rationale for doubling the array versus just increasing it by a small amount, you might want to check out these lecture slides. The pictures toward the end might be very relevant.

希望这有帮助！

这篇关于维基百科表示在动态数组末尾插入一个项目的复杂性是O（1）摊销？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！