c++ - 动态数组的时间复杂度

Question

我对动态数组的时间复杂度有点困惑。本文中here它指出动态数组的插入和删除的时间复杂度是O(n)。我想知道为什么插入和删除动态数组会出现这种情况。

我对为什么插入动态数组可能是 O(n) 的理解是因为一旦插入一个元素，其他元素需要移回，即 O(n)。但是我在其他地方读到，这是因为如果你用完了空间，那么额外的空间会被重新分配，之前的项目被复制并粘贴到新的内存位置。我想知道哪个推理是正确的。另外，我对删除时间复杂度为 O(n) 的数组的推理是，一旦删除了一个元素，其他元素就会向前移动以覆盖已删除的项目空间。然而，文章再次给出了另一个答案，并指出由于搜索是 O (n) 在动态数组中因此删除是 O(n) 在动态数组中，因为在删除元素之前搜索元素。如果有人能澄清这种混淆，我将不胜感激。谢谢。

Answer 1

My understanding of why the insertion of Dynamic Array might be O(n) is because once an element is inserted the other elements need to be moved back

正确。

Also my reasoning for an array having a time complexity of O(n) for deletion is that once an element is deleted other elements are moved forth to cover the deleted items space.

正确。

However I read somewhere else the reason for this is because in case you run out of space then extra space is reallocated the previous items copied and pasted into the new memory location.

我认为您在这里混淆了一些东西。也许您正在考虑如果在末尾 插入并且数组溢出会发生什么情况。在那种情况下，您还必须将整个数组复制到一个更大的新位置。但是这个成本可以计入为发生这种情况而必须发生的末尾的插入。所以最后插入是"amortized O(1)" .

完全相同的推理适用于删除。

总结一下:在数组的 k 位置插入/删除有 amortized complexity O(n - k)。特别地，任意位置的插入/删除是O(n)，最后的插入/删除是O(1)。

However again the article gives another answer and states that since searching is O(n) in Dynamic array thus deleting is O(n) in dynamic array since an element is searched before its deleted

搜索与插入/删除无关。在考虑插入/删除成本时，您通常假设您已经知道要插入/删除的位置。