根据维基百科关于动态数组的文章，在数组末尾插入/删除是 O(1)，而从中间插入/删除是 O(n)。为什么会这样？
另外 - 如果我有一个包含 5 个元素的动态数组，并且我在位置 6 插入一个新元素，则操作为 O(n)，而如果我使用该函数附加到数组的末尾，则为 O(1)。假设数组在任何一种情况下都不需要调整大小，这不是相同的操作吗？或者附加到动态数组是否真的在位置 6 之外的某个地方插入了新元素？
谢谢！
编辑：我认为我的主要困惑是在数组末尾插入和在相当于数组末尾的特定位置插入之间的区别。
我想指向数组末尾的内存地址的指针很方便，这就是附加操作很快的原因。相反，如果我指定一个精确的位置（即使它是数组的末尾），它不会知道在那个位置插入就等于使用上述内存地址，所以它必须遍历整个数组，是吗？
要在数组的末尾插入，您只需将项目放在那里。
要插入到数组的中间，您需要将该点之后的项目向上移动一个。
要从数组的末尾删除，只需将其计数减一即可。
要从中间删除，您必须这样做并将其他项目向下移动。
正是这种转变将其变成了 O(n)。
数量级完全取决于“动态数组”实际上是哪种数据结构（“动态数组”不是严格定义的数据结构，它更多的是通过使用特定数据结构实现的预期结果）。您给出的示例将通过使用链表实现的动态数组来反映。如果列表结构保留指向最终元素的指针，则添加到末尾可能是 O(1)。插入（无论索引如何）需要遍历链表，这意味着每个节点执行一次操作，直到所需索引为止。
这很简单：
在中间插入涉及将后面的每个元素移动 1。要在最后插入，如果保留了额外的空间，则项目只是存储在那里，但如果没有分配新空间。因此这个操作是在摊销的常数时间内完成的。
添加到亚当罗宾逊的精彩总结：这不仅仅是理论。我见过许多情况，其中动态数组是通过重复附加到数组末尾来构造的。这会(N**2)降低性能，因为数组需要反复重新分配，迫使其每个成员都被复制到新的数组结构中。重新分配可能仅发生在 1/10 的附加操作上，但这已经够糟糕了，而且在(N**2)性能方面仍然不理想。
vector::reserve(N)在 STL 中，可以通过在写入向量之前调用来避免这种性能损失；但是这一步经常被忽视。
实际上，它不是 Big-O 而是Big-Theta。