动态数组放置元素的时间复杂度

Question

在笔试中，我遇到这样的问题：

当一个动态数组满的时候，它会扩展到双空间，就像2到4，16到32等等。但是，在数组中放置一个元素的时间复杂度是多少呢？

我认为不应该考虑扩展空间，所以我编写了O(n)，但我不确定。

答案是什么？

Answer 1

这取决于所提出的问题。

如果问题要求一个插入所需的时间，那么答案是O(n)，因为大-O意味着“最坏的情况”。在最坏的情况下，您需要扩展数组。增长数组需要分配一个更大的内存块(正如您经常说的那样，大小是原来的2倍，但可能使用大于1的其他因素)，然后复制整个内容，即n个现有元素。在Java等一些语言中，额外的空间也必须初始化。

如果问题的摊销时间，那么答案是O(1)。另一种说法是，n的成本是O(n)。

这怎么可能呢？每个加法都是O(n)，但其中n也需要O(n)。这就是摊销的美。为了简单起见，假设数组从1开始，每次填充时增长2倍，所以我们总是复制一个由2个元素组成的幂。这意味着生长成本是第一次增长1次，第二次增长2次等。一般说来，生长n元素的总成本是TC=1+2+4+...n。嗯，不难看出TC = 2n-1。如果n= 8，则TC=1+2+4+8=15=2*8-1。因此，TC与n或O(n)成正比。

无论初始数组大小还是增长因子，只要因子大于1，这种分析都是有效的。

如果你的老师很好，他或她会以模棱两可的方式问这个问题，看看你是否可以同时讨论这两个问题。

Answer 2

为了扩大数组大小，您不能简单地“将更多的添加到末尾”，因为您将更有可能得到“分段错误”类型的错误。因此，即使作为平均值，它采取θ(1)步骤是因为您有足够的空间，如果O表示法是O(n)，因为您必须将旧数组复制到一个新的更大的数组中(为此您分配了内存)，这就需要n steps...generally。另一方面，通常情况下，您可以更快地复制数组，因为它只是一个来自连续空间的内存副本，这应该是最佳场景中的一个步骤，即页面(OS)可以占据整个数组。最后..。数学上，即使考虑到我们正在做n/ (4096 * 2^10) (4KB)步骤，它仍然意味着O(n)的复杂性。