为什么在动态数组O(n)时间复杂度结束时删除项？

Question

我目前正在阅读我的教科书,我很困惑为什么动态数组需要O(n)时间来删除最后的项目.我知道从任何其他索引中删除一个项目是O(n),因为你必须复制所有数据并移动它们以填补空白,但如果它最后不是我们只是减少计数并设置索引喜欢0还是null？我在书中加了一张照片.这很奇怪,因为它说索引是O(1)所以我们必须知道项目的位置,所以我们不必像链表一样遍历数组.

Answer 1

首先,让我们通过"动态数组"查看书籍的含义:

动态数组(也称为可增长数组,可调整大小数组, 动态表或数组列表)是一种随机访问,可变大小的列表数据结构,允许添加或删除元素.[...]
注意:我们将在Stacks,Queues和Hashing章节中看到动态数组的实现.

由此我们了解到,数组列表是"动态数组"的示例,正​​如本书的作者所定义的那样.

但进一步看,这本书提到:

一旦该数组变满,就创建一个比原始数组大两倍的新数组.同样,如果数组中的元素小于一半,则将数组大小减小到一半.

(我强调的是)

Java ArrayList不会这样做 - 当删除元素时,它不会减少存储空间.但作者正在谈论(或认为ArrayList确实如此)减少阵列大小.在这种情况下,从最糟糕的情况来看,你可以说复杂性是O(n)因为减小尺寸涉及将n元素复制到简化的数组.

结论:

虽然Java ArrayList实现并不是这样,但是当本书的作者谈到"动态数组"在必要时"减少数组大小"时,那么数组末尾删除的最坏情况确实很复杂O(n).

Answer 2

这个条目似乎也是如此

1. 不正确,或
2. 是的,但有误导性.

你是完全正确的,你可以在动态数组中的最终位置销毁对象,然后减小大小以删除最后一个元素.在动态数组的许多实现中,有时需要执行调整大小操作以确保分配的数组的大小在元素数量的某个常数因子内.如果发生这种情况,那么是的,您需要创建一个新数组,复制旧元素,然后释放前一个数组,这需要花费时间O(n).但是,您可以证明这些调整大小非常罕见,以至于从末尾执行删除的平均成本是O(1).(在更技术性的意义上,我们说从末端删除元素的摊销成本是O(1)).也就是说,只要您只关心执行一系列操作的总成本而不是任何单个操作的成本,那么假装每个操作花费您的时间O(1)就没有错.

我会说你最有可能看到材料中的拼写错误.看看他们的条目是否附加到最后,它区分了非完整和完整的案例,我认为这可能是一个复制/粘贴错误.在表的引导之后,应该说"O(1)如果数组不是'太空,'O(n)否则." 但同样,请记住,每个操作的摊销效率为O(1),这意味着这些可怕的O(n)术语实际上不太可能在实践中烧伤你,除非你处于每个操作需要的专门环境中工作真的很快.