我对为什么插入动态数组可能是O（n）的理解是因为一旦插入了一个元素，其他元素就需要移回来
正确。
同样，我对一个时间复杂度为O（n）的数组进行删除的推理是，一旦删除了一个元素，其他元素就会向前移动以覆盖删除项空间。
正确。
然而，我在其他地方读到的原因是，如果你用完了空间，那么额外的空间被重新分配之前的项目复制和粘贴到新的内存位置。
我想你在这里混淆了一些东西。也许你在想，如果你在 end 插入，数组溢出会发生什么。在这种情况下，你 * 还 * 必须将整个数组复制到一个新的，更大的位置。但是这样做的成本可以计入在末尾的插入，这必须发生这种情况。所以在末尾的插入是"amortized O(1)"。
同样的推理也适用于删除。
总结如下：在数组的位置 k 的插入/缺失为amortized complexityO（n-k），特别是在任意位置的插入/缺失为O（n），在末端的插入/缺失为O（1）。
然而，这篇文章再次给出了另一个答案，并指出，由于在动态数组中搜索是O（n），因此在动态数组中删除是O（n），因为在删除元素之前搜索元素
搜索与插入/删除无关。当考虑插入/删除成本时，通常假设您已经知道要插入/删除的位置。

假设你有一个动态数组，每次需要扩展时它的大小都会翻倍，假设你从一个大小为1的数组开始，并添加1个元素，我将用x来表示向数组中写入数据的行为：

x

现在让我们添加第二个元素，强制数组扩展并复制前一个项目：

x
x x

现在数组的大小为2。我添加了另一个元素，强制将大小调整为4并复制2个元素：x x x x x x
我添加了第四个元素，然后又添加了第五个元素，这将迫使重新调整大小为8：

x
        x
    x   x
  x x   x
x x x x x

现在，让我重写最后一个“塔”，将其高度分布在两列上，这代表了一种“摊余成本”。

x x x
  x x x x
x x x x x

下一次我们需要调整大小是当我们插入第9个项目。这一次，我将代表的努力已经与摊销的复制8个项目比以前的8个插入。

x x x x x x x
  x x x x x x x x
x x x x x x x x x

一般来说，每次复制复制操作都是在完成2的连续幂次之后进行的，复制的项目数是2的幂次，是自上次复制操作以来插入次数的一半，所以这意味着，摊分后，每次插入操作的平均数需要插入和两次复制，即总共3次。这使得成本为3n，也就是O（n）。关键是摊销。将 n 个元素插入动态数组的成本（在扩展时其大小加倍）是 * 突发的 ，但是， 平均 *，你可以把每一次插入看作是“支付成本”或“税收”，因为当数组扩展时，将来可能必须执行拷贝。