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

Question

“因此，插入 N 个元素总共需要 O(N) 的工作量。每次插入平均为 O(1)，但在最坏的情况下，每次插入都需要 O(N) 的时间。”这句话可以在 Cracking the Coding Interview 中找到。我有点理解这句话，尽管它有一点让我恼火。在好的日子里，摊销插入是 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
• #resize 完成 = 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