每次push_back重分配时，std::vector::push_back的时间复杂度是常数还是线性？

直接给结论：这种修改后的push_back摊还复杂度不再是O(1)，而是O(n)。下面一步步解释为什么：

先搞懂摊还复杂度的本质 #

摊还复杂度看的不是单次操作的最坏情况，而是连续执行n次操作的总时间，再平均到每次的成本。原std::vector的O(1)摊还复杂度，核心是扩容策略带来的总时间可控。

原翻倍扩容的总时间计算 #

原实现里，std::vector每次扩容把容量翻一倍（比如从1到2，2到4，4到8...）。假设我们做n次push_back：

• 第1次扩容：容量从0变1，不用拷贝元素，耗时O(1)
• 第2次扩容：容量从1变2，拷贝1个元素，耗时O(1)
• 第4次扩容：容量从2变4，拷贝2个元素，耗时O(2)
• 第8次扩容：容量从4变8，拷贝4个元素，耗时O(4)
• ...

所有扩容的拷贝总耗时是1+2+4+...+n/2，这个和小于2n，所以n次操作总耗时是O(n)，平均下来每次就是O(1)的摊还复杂度。

每次都扩容的总时间计算 #

现在改成每次push_back都重分配（比如每次容量只加1），n次操作的总耗时就完全不一样了：

• 第1次：分配容量1，无拷贝，O(1)
• 第2次：分配容量2，拷贝1个元素，O(1)
• 第3次：分配容量3，拷贝2个元素，O(2)
• 第4次：分配容量4，拷贝3个元素，O(3)
• ...
• 第n次：分配容量n，拷贝n-1个元素，O(n-1)

把这些耗时加起来，总和是0+1+2+...+(n-1) = n(n-1)/2，这是**O(n²)**的总耗时。平均到每次操作，摊还复杂度就是O(n)——随着n增大，每次操作的平均耗时会线性增长，根本达不到O(1)。

关于“常数部分”的说明 #

你提到“每次push_back都需遍历向量中所有元素”，这里的遍历（拷贝）的常数开销其实不是重点。摊还复杂度关心的是时间随数据规模增长的量级，哪怕拷贝每个元素的速度再快，总耗时是平方级的，摊还后的平均耗时还是会跟着n变大而线性上升，不可能维持O(1)的水平。

内容的提问来源于stack exchange，提问作者dau_sama