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

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，此分析都有效。

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