arrays - 有人可以向我解释数组的 Big Oh 复杂性吗？我不太明白他们是如何工作的

Question

我在很大程度上理解链表的复杂性。在最坏的情况下访问一个项目是 O(n)，因为它可能在末尾或不存在。添加到未排序的链表的复杂度为 O(1)，因为您只需将其添加为头部即可。

但是对于数组，我很困惑。我已经阅读了很多关于访问效率如何 (O(1)) 的内容，但是添加不一定，删除也不一定。这是为什么？

是因为加法并不总是在最后吗？那里会是 O(1)，对吗？但是如果它在另一个点，你就必须移动项目，这将是 O(n)？这是在“幕后”发生的，可以用高级语言来说，对吧？它正在移动内存位置，这就是复杂性开始的地方？

删除会导致我收集的数据有差距吗？而且还得填？

基本上，如果我有一个包含 10 个项目的数组，并且我要在第 5 个索引点添加一个项目，它是否必须将索引 5 和更高索引点的所有项目复制到更高的索引点，导致操作复杂度为 O(n)？

如有任何澄清，我们将不胜感激。

Answer 1

插入(例如插入数组的中间)是 O(n) 因为正如您所说，您需要将所有后续元素移动到右侧。因此，如果您在第一个位置插入，则必须将现有元素的所有 n 移过去以腾出空间，最坏情况下的成本为 n。平均而言，假设您在随机位置插入，您将移动 (n/2) 个元素。

追加(到数组末尾)也是 O(n) 因为我需要重新分配。如果您的数组存在于一 block 内存中，该内存块已分配为大于数组的当前大小，这不是问题；您只需(恒定时间)写入内存中的下一个位置。但最终你会用完房间。然后，您需要分配一个更大的新内存块，并将所有现有元素复制到其中。所以最坏情况下的净成本是 n+1(n 份，加上 1 追加)这给了你 O(n )。 (还有分配内存的任何幕后成本。)为了避免这种成本，许多语言和库为您提供了在数组中预分配空间的选项，以覆盖您希望在数组中看到的最大元素数你的申请;这确保不会有任何重新分配，除非您最终添加的元素数量超过预期数量。

删除是 O(n) 因为(如您所说)您需要将删除元素之后的所有内容向左移动一个空格。如果您从第一个位置删除，则必须将所有 n-1 剩余元素移过去，在最坏的情况下为您提供 O(n)。 (如果您从最后 位置删除，那只需要常数时间。)