为什么动态数组必须以几何方式增加其容量以获得 O(1) 摊销 push_back 时间复杂度？

Question

我了解到动态数组，例如std::vector，在达到其容量时会将其容量加倍，以使push_back操作 O(1) 分摊时间。

但是，为什么首先需要这样做？不是在末尾为一个元素分配空间vector并将新元素复制到 O(1) 吗？

Answer 1

如果要在数组末尾分配空间，则只有在该位置的内存可用时才有效。其他东西可能已经存在，或者该内存可能无法使用。所以调整数组大小的方式（一般来说）：

1. 创建一个新的更大的数组，

2. 将原始数组中的元素复制到更大的数组中，然后

3. 销毁原始数组。

如您所见，当您增加数组的大小时，您将支付与数组原始大小成正比的成本。

因此，如果您从一个包含一个元素的数组开始并添加第二个元素，则必须将第一个元素复制到另一个数组中。如果添加第三个元素，则必须复制其他两个元素。如果添加第四个元素，则必须复制前三个元素。这加起来为 1+2+3...+N，它等于 N(N+1)/2，在 O(N ² ) 中。请参阅算术级数（维基百科）

如果您以几何级数调整数组大小，您仍然必须每次都复制元素，但复制的次数更少。

如果您通过加倍数组来调整大小，那么当您获得大小为 N 的两个幂时，N/2 将被复制 0 次，N/4 将被复制一次，N/8 将被复制两次，依此类推. 0N/2 + 1N/4 + 2N/8 + 3N/16... 的总和是 O(N)。见几何系列（维基百科）

您不需要选择加倍，您可以选择其他一些因素，例如 1.5 倍。选择不同的因子不会改变渐近复杂度，但会改变实际性能。