堆栈动态数组实现的复杂性

Question

在典型的动态数组实现中,当没有新元素的空间时,我们将堆栈加倍.在这种情况下,推动操作的平均时间加倍是O(n).

推送的复杂性是什么,如果不是加倍,我们将堆栈大小增加了(n + k)？

我的方法如下

假设堆栈为空,并且k = 10,我们将堆栈增加到10个元素.在10个元素之后,我们使它成为20个元素,依此类推.

复制元素的平均时间是10 + 20 + 30 + ...

因此推送的平均时间必须是O(n)的顺序？

我的方法是否正确？

Answer 1

你的计算不正确。动态数组的典型实现将其大小加倍（或更一般地说，将其大小增加x %）是有原因的。

如果将大小从 1 增加到 n = 2 ⁱ，则复制的元素总数为 1 + 2 + 4 + 8 + 16 + ... + 2 ⁱ。如果将其相加，则它小于 2 ⁱ⁺¹，因此总时间复杂度为 O(n) ，一次插入的分摊时间复杂度为 O(1)。如果 n 不是 2 的幂，计算会稍微复杂一些，但结果是一样的。

另一方面，如果将大小增加 k，从 0 到 n = i * k，则复制的元素总数为 k + 2k + 3k + ... + ik。如果你对这个求和，它将是 (ik + k) * (ik / k) / 2 = O(n ² )。并且一次插入的摊销复杂度将为 O(n)。

因此，您的解决方案比将尺寸加倍要糟糕得多。

Answer 2

根据您增加存储的方式并且 k 足够小，对于所有情况或其他情况，它可能是 O(1)。

我所说的“如何”，是指在托管语言中，创建一个大小为 n + k 的新数组，然后将旧数组（大小为 n）复制到新数组，最后将旧数组的引用替换为新数组一。那将是：O(1)（数组创建，这是一个假设）+ O(n)（数据复制）+ O(1)（引用更改）。我们忽略垃圾收集器的执行，因为它非常依赖于实现。在非托管语言中，可以使用类似的方法来realloc保留旧元素，而无需复制，因为新存储占用相同的内存区域，仅扩展到所需项目的数量。在本例中，所有情况的复杂度都是 O(1)。但请注意，有时由于内存碎片，将存储扩展到所需项目的数量是不可能的，因此采用类似于托管语言的方法（但通过realloc实现隐式完成）。对于这一点，复杂性与托管语言相同：O(n)。

这就是从实际角度出发的答案，希望您能通过上述答案从分析的角度找到答案。祝你好运。