我有点困惑时动态数组的复杂性。 在这篇文章中这里它指出，插入和删除动态数组的时间复杂度为O（n）。我想知道这是为什么，插入动态数组和删除的情况。

我为什么动态数组的插入可能为O理解（n）是因为一旦一种元素插入其他元素需要被移动回来，那是O（n）。不过我读别的地方这样做的原因是因为如果你运行的空间那么额外的空间被重新分配，复制并粘贴到新内存location.I想知道哪个推理是正确的previous项目。另外我推理为O（N）为删除的时间复杂度的数组是，一旦一个元素被删除，其它元素来回移动以覆盖删除的项目space.However再次文章给出了另一个答案，并指出，由于搜索是O在动态数组从而删除（N）是O（n）的动态数组，因为搜索的元素它删除。我想AP preciate，如果有人可以澄清这种混乱。谢谢你。

我为什么动态数组的插入可能为O理解（n）是因为一旦一种元素插入其他元素需要被移回

正确的。

也是我的推理有O（N）为删除的时间复杂度的数组是，一旦一个元素被删除，其它元素来回移动以覆盖删除的项目空间。

正确的。

不过，我看别的地方这样做的原因是因为如果你运行的空间那么额外的空间被重新分配，复制并粘贴到新的内存位置previous项目。

我想你混淆的东西在这里。也许你正在考虑，如果你在的结束的和阵列溢出插入会发生什么。在这种情况下，你的也的有整个阵列复制到一个新的，更大的位置。但成本为此可以被充电到一个必须发生这种情况发生了插入在末端。因此，在插入到底是摊销O（1）。

确切同样的道理适用于删除。

要总结：插入/缺失位置数组的 K 的有摊销复杂 为O（n - K）的。特别是，插入/缺失在任意位置为O（n）和插入/缺失在末端是O（1）。

不过再次文章给出了另一个答案，并指出，由于搜索是O（n）的动态数组从而删除是O（n）的动态数组，因为一个元素之前搜索其删除

搜索无关，因为与插入/缺失。当考虑插入/缺失成本，你通常会假设你已经知道位置，要插入/删除。

I am a bit confused about time complexity of Dynamic Arrays. In this article here it states that the time complexity of insertion and deletion of Dynamic Array is O(n). I wanted to know why that is the case for insertion and deletion of dynamic array.

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 and that is O(n). 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.I wanted to know which reasoning is correct. 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 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. I would appreciate it if someone could clarify this confusion. Thanks.

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

Correct.

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.

Correct.

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.

I think you're confusing something here. Maybe you are thinking about what happens if you insert at the end and the array overflows. In that case you also have to copy the whole array to a new, larger location. But the cost for this can be charged to the insertions at the end that must have happened for this situation to occur. So insertion at the end is "amortized O(1)".

The exact same reasoning works for deletion.

To summarize: Insertion/deletion at position k of an array has amortized complexity O(n - k). In particular, insertion/deletion at an arbitrary position is O(n) and insertion/deletion at the end is 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

Searching has nothing to due with insertion/deletion. When considering insertion/deletion cost, you usually assume that you already know the position where you want to insert/delete.