c++ - 为什么动态数组必须以几何方式增加其容量以获得 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²)。参见 Arithmetic Progression (Wikipedia)

如果您按几何级数调整数组的大小，您仍然需要每次都复制元素，但您复制它们的次数更少。

如果你通过加倍数组来调整大小，那么当你得到一些大小 N 的幂时，N/2 将被复制 0 次，N/4 将被复制一次，N/8 将被复制两次，等等。 0N/2 + 1N/4 + 2N/8 + 3N/16... 的总和在 O(N) 中。参见 Geometric Series (Wikipedia)

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