c++ - 可调整大小的数组和摊销运行时

Question

“因此，插入 N 个元素总共需要 O(N) 工作时间。每次插入平均需要 O(1) 时间，但在最坏的情况下，每次插入都会花费 O(N) 时间。”这句话可以在《破解编码面试》中找到。我有点理解这个说法，尽管其中的一些小事情让我感到恼火。在好的日子里，摊销插入是 O(1)。这仅仅意味着当可调整大小的数组不需要调整大小时，插入某些内容只需 O(1)。这很清楚。但是，在糟糕的一天，当我们用完空间时，我们将需要 O(N) 来插入额外的元素。然而，我不同意上面的说法，它说在最坏的情况下某些插入需要 O(N) 。难道不应该说，在最坏的情况下，一次插入需要 O(N) 吗？

为了让这一点更清楚，这是我所说的一个例子。

假设我们有一个可调整大小的数组，但该数组的大小为 4。现在假设要插入 5 个元素，我们将需要 O(1)、O(1)、O(1)、O(1)，但是一旦我们到达最后一个元素，我们就必须将所有这些元素复制到一个新数组中，这个过程将给我们带来 O(N) 的成本。

有人可以帮我澄清一下吗？我不明白为什么这本书说某些情况需要 O(N)，而当我们在旧数组中的空间耗尽时只需要将所有元素复制到新数组中一次。

Answer 1

考虑在可调整大小的数组中进行 N 次插入的成本(我将在此处使用波浪号表示法):

• N 次插入的成本 = 新元素插入的成本 + 调整大小的成本

新元素插入的成本

这只是在数组中插入新元素的成本乘以插入新元素的次数，即 N:

• 新元素插入的成本 = 1 * N

调整大小的成本

假设您有一个 64 个单元格的数组。那么，这意味着数组的大小已调整为:

• 数组大小 = 1 -> 2 -> 4 -> 8 -> 16 -> 32 -> 64
• #调整大小完成 = 6

64 元胞数组已调整大小 6 次，即调整大小发生了 log2(64) 次。一般来说，现在我们知道对于 N 次插入，我们将执行 log2(N) 调整大小操作。

但是我们在每次调整大小时做了什么？我们将把数组中已经存在的元素复制到新调整大小的数组中:在调整大小“i”时，我们将复制多少个元素？ 2^i。与前面的例子:

• 调整数字 1 的大小 = 1 -> 2:复制 1 个元素
• 调整数字 2 的大小 = 2 -> 4:复制 2 个元素
• 调整数字 3 = 4 -> 8 的大小:复制 4 个元素
• ......
• 调整数字 6 = 32 -> 64 的大小:复制 32 个元素

所以:

• 调整大小的成本 = 总和(从 i=1 到 log2(N))2^i = 2(N-1)

结论

• N 次插入的成本 = 新元素插入的成本 + 调整大小的成本 = N + 2(N-1) ~ 3N