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

Question

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

如果我们将堆栈大小增加 (n+k) 而不是加倍，那么推送的复杂度是多少？

我的做法如下

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

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

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

我的方法正确吗？

Answer 1

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

如果将大小从 1 增加到 n = 2i，则复制的元素总数为 1 + 2 + 4 + 8 + 16 + ... + 2i。如果你把它加起来，它小于 2i+1，所以总时间复杂度是 O(n) 和 amortized time complexity一次插入是 O(1)。如果 n 不是 2 的幂，计算会稍微复杂一些，但结果是一样的。

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

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