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