容量按完全平方数扩容的动态容器push_back操作的复杂度是多少？

最坏情况时间复杂度 #

单次操作的最坏情况出现在触发扩容的那次插入：当容器当前容量为k²，插入第k²+1个元素时，需要将所有k²个元素复制到新的容量为(k+1)²的容器中，再插入新元素。这一步的时间成本为O(k²)。当元素总数n趋近于(k+1)²时，k≈√n，因此单次操作的最坏时间复杂度为O(n)。

均摊时间复杂度 #

通过总时间成本除以总操作次数推导：

• 假设执行了n次插入操作，对应的最大扩容步是到m²，其中m² ≤ n < (m+1)²，m≈√n。
• 总时间成本 = 所有插入的基本成本（n次，每次O(1)） + 历次扩容的复制成本（1²+2²+3²+…+m²）。
• 根据平方和公式，1²+2²+…+m² = m(m+1)(2m+1)/6，代入m≈√n，可得复制总成本为O(n^(3/2))。
• 总时间成本为O(n) + O(n^(3/2)) = O(n^(3/2))，均摊到n次操作后，每次的均摊时间复杂度为O(√n)。

你的错误点 #

你误将两次扩容的容量差（2n+1）当作计算复杂度的核心，但实际上扩容的复制成本是前一次的容量（n²），而非容量差。需要结合总操作次数和总复制成本推导均摊复杂度，而非仅看单次扩容的差值。

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