为什么在插入中间插入动态数组O（1）的末尾是O（n）？

Question

根据维基百科关于动态数组的文章，在结尾插入/删除数组是O（1），而从中间插入/删除是O（n）。究竟是为什么？

另外 - 如果我有一个包含5个元素的动态数组，并且我在第6位插入一个新元素，则操作为O（n），而如果我使用该函数追加到数组的末尾则为O（1） 。假设数组在任何一种情况下都不需要调整大小，这不是相同的操作吗？或者附加到动态数组是否真的在位置6之外的某处插入新元素？

谢谢！

编辑：我认为我的主要困惑是插入数组末尾和插入等效于数组末尾的特定位置之间的区别。

我认为指向数组末尾的内存地址的指针很方便，这就是追加操作很快的原因。相反，如果我指定一个精确的位置（即使它是数组的末尾），它也不会知道在那个位置插入等于使用前面提到的内存地址所以它必须遍历整个数组，嗯？

Answer 1

数量级完全取决于“动态阵列”的数据结构类型。实际上（“动态数组”不是严格定义的数据结构，它更多是通过采用特定数据结构实现的期望结果）。您给出的示例将通过使用链接列表实现的动态数组反映。如果列表结构保留指向最终元素的指针，则添加到最后可以是O（1）。插入（无论索引如何）将需要遍历链表，这意味着每个节点一个操作直到所需的索引。

Answer 2

要在数组的末尾插入，只需将项目放在那里。

要插入数组的中间，您需要在该点之后将项目向上移动一个。

要从数组的末尾删除，只需将其计数减一。

要从中间删除，您必须执行并将其他项目向下移动。

shift 将其变为O（n）。

Answer 3

这很简单：

在中间插入涉及将每个后面的元素移动1。 要在最后插入，如果有预留的额外空间，则该项目仅存储在那里，但如果没有，则分配新空间。因此，此操作在摊销常数时间中完成。

Answer 4

添加亚当罗宾逊的优秀摘要：这不仅仅是理论。我已经看到了通过重复追加到数组末尾构造动态数组的任何情况。这可以解决o （N ** 2）性能，因为重复需要重新分配数组，强制将每个成员复制到新的数组结构中。重新分配可能只发生在附加操作的1/10，但这已经够糟糕了，并且仍然是o （N ** 2）性能。

在STL中，可以通过在写入向量之前调用 vector :: reserve（N）来避免这种性能损失;但这一步往往被忽视。

Answer 5

实际上，它不是Big-O，而是 Big-Theta