std::vector::push_back 的这些变体是恒定的还是线性的？
Are these variants of std::vector::push_back constant or linear?
我们都知道 std::vector::push_back 具有恒定（摊销）的复杂性。
它是常数，因为我们说摊销成本可以忽略不计，每次都会翻倍。重新分配是线性复杂度。
让我们稍微更改一下 std::vector 界面，以不同有趣的方式强制重新分配。
每 push_back
重新分配
如果我们在每个 push_back 上重新分配，push_back 仍然是 O(1)（摊销）吗？
每 push_back 我们遍历向量中的所有项目
我想常量部分会落在这里并且 push_back 和重新分配都是 O(N)
仅在奇数编号上重新分配 push_back
如果我们每隔 push_back 重新分配，push_back 是否仍然 O(1)（摊销）？
与其他变体相比，push_back 仍然是线性的 O(N) 吗？或者我们仍然可以假设它是固定摊销的吗？
In this case, would push_back still be constant?
没有。是O(realloc(n))，也就是O(n)。
In this case, would push_back still be linear O(N)?
是的。 最佳情况 的性能是 O(1)，最坏情况的性能 O(realloc(n))，即 O(n)。如果你调用 push_back N 次，你将调用 realloc N/2 次，每次使用 O(N)，所以平均我们有 O(N*(N/2)/N) = O(N/2) = O(N).
将其与双倍大小 push_back 进行比较，在 N push_back 上我们只会调用 realloc log(N) 次。有关详细说明，请参阅 this post。
我们都知道 std::vector::push_back 具有恒定（摊销）的复杂性。
它是常数，因为我们说摊销成本可以忽略不计，每次都会翻倍。重新分配是线性复杂度。
让我们稍微更改一下 std::vector 界面，以不同有趣的方式强制重新分配。
每 push_back
重新分配
如果我们在每个 push_back 上重新分配，push_back 仍然是 O(1)（摊销）吗？
每 push_back 我们遍历向量中的所有项目
我想常量部分会落在这里并且 push_back 和重新分配都是 O(N)
仅在奇数编号上重新分配 push_back
如果我们每隔 push_back 重新分配，push_back 是否仍然 O(1)（摊销）？
与其他变体相比，push_back 仍然是线性的 O(N) 吗？或者我们仍然可以假设它是固定摊销的吗？
In this case, would
push_backstill be constant?
没有。是O(realloc(n))，也就是O(n)。
In this case, would
push_backstill be linearO(N)?
是的。 最佳情况 的性能是 O(1)，最坏情况的性能 O(realloc(n))，即 O(n)。如果你调用 push_back N 次，你将调用 realloc N/2 次，每次使用 O(N)，所以平均我们有 O(N*(N/2)/N) = O(N/2) = O(N).
将其与双倍大小 push_back 进行比较，在 N push_back 上我们只会调用 realloc log(N) 次。有关详细说明，请参阅 this post。