为什么动态数组必须以几何方式增加其容量以获得 O(1) 分摊 push_back 时间复杂度？
Why do dynamic arrays have to geometrically increase their capacity to gain O(1) amortized push_back time complexity?
我了解到动态数组，例如 std::vector，在达到其容量时将其容量加倍以使 push_back 操作 O(1) 摊销时间。
但是，为什么首先需要这样做？不是在 vector 末尾为一个元素分配 space 并在那里复制新元素已经 O(1) 吗？
如果你可以在最后再分配 space 一个元素，然后将新元素复制到那里，那确实是 O(1)。
但是标准库没有提供这样做的方法，主要是因为您不能依赖实际能够做到这一点。
所以通常最终发生的事情是分配一个全新的内存块，将现有数据从现有块复制（或移动）到新块，然后将新元素添加到新块。 copying/moving 从现有块到新块的所有元素的额外步骤是线性的，这意味着添加新元素是线性的。
这里的困难在于 std::vector 将其内容保存在 连续的 内存中。为单个附加元素分配内存并将其移动到那里是不够的。您需要保证您有足够的内存用于整个容器，所有这些都集中在一个地方。每次分配都可能需要复制所有以前的内容以保持连续性，因此实际上不一定需要 O(1) 才能为单个附加元素获得足够的内存。
如果你想在数组的末尾分配 space，那只有在该位置的内存可用时才有效。其他东西可能已经存在，或者该内存可能无法使用。所以调整数组大小的方式（在 general 中）：
创建一个更大的新数组，
将原数组中的元素复制到更大的数组中，
销毁原数组
如您所见，当您增加数组的大小时，您付出的代价与数组的原始大小成正比。
因此，如果您从一个包含一个元素的数组开始并添加第二个元素，则必须将第一个元素复制到另一个数组中。如果添加第三个元素，则必须复制其他两个元素。如果添加第四个元素，则必须复制前三个。这样加起来就是1+2+3...+N，等于N(N+1)/2，也就是O(N2)。参见 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 倍。选择不同的因子不会改变渐近复杂度，但会改变实际性能。
我了解到动态数组，例如 std::vector，在达到其容量时将其容量加倍以使 push_back 操作 O(1) 摊销时间。
但是，为什么首先需要这样做？不是在 vector 末尾为一个元素分配 space 并在那里复制新元素已经 O(1) 吗？
如果你可以在最后再分配 space 一个元素，然后将新元素复制到那里，那确实是 O(1)。
但是标准库没有提供这样做的方法，主要是因为您不能依赖实际能够做到这一点。
所以通常最终发生的事情是分配一个全新的内存块，将现有数据从现有块复制（或移动）到新块，然后将新元素添加到新块。 copying/moving 从现有块到新块的所有元素的额外步骤是线性的，这意味着添加新元素是线性的。
这里的困难在于 std::vector 将其内容保存在 连续的 内存中。为单个附加元素分配内存并将其移动到那里是不够的。您需要保证您有足够的内存用于整个容器，所有这些都集中在一个地方。每次分配都可能需要复制所有以前的内容以保持连续性，因此实际上不一定需要 O(1) 才能为单个附加元素获得足够的内存。
如果你想在数组的末尾分配 space，那只有在该位置的内存可用时才有效。其他东西可能已经存在，或者该内存可能无法使用。所以调整数组大小的方式（在 general 中）：
创建一个更大的新数组，
将原数组中的元素复制到更大的数组中，
销毁原数组
如您所见，当您增加数组的大小时，您付出的代价与数组的原始大小成正比。
因此，如果您从一个包含一个元素的数组开始并添加第二个元素，则必须将第一个元素复制到另一个数组中。如果添加第三个元素，则必须复制其他两个元素。如果添加第四个元素，则必须复制前三个。这样加起来就是1+2+3...+N，等于N(N+1)/2，也就是O(N2)。参见 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 倍。选择不同的因子不会改变渐近复杂度，但会改变实际性能。