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

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

然而，为什么首先需要这样做呢？没有为末尾的一个元素分配空间vector并复制新元素已经O(1)了？

如果您想在数组末尾分配空间，则仅当该位置的内存可用时才有效。可能已经有其他东西了，或者该内存可能无法使用。所以调整数组大小的方式是有效的（在general):

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

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

3. 销毁原来的数组。

正如您所看到的，当您增加数组的大小时，您付出的成本与数组的原始大小成正比。

So if you start with an array with one element and add a second element, you have to copy the first element into another array. If you add a third element, you have to copy the other two elements. If you add a fourth element, you have to copy the first three. This adds up to 1+2+3...+N, which is equal to N(N+1)/2, which is in O(N²). See Arithmetic Progression (Wikipedia) https://en.wikipedia.org/wiki/Arithmetic_progression

如果以几何级数调整数组大小，每次仍然需要复制元素，但只是复制它们fewer times.

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

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