cpp vector.push_back()时间复杂度证明

vector 是 cpp 中常用的一种容器，是一种可以动态扩容的数组。他在每次插入的时候，当它的 capacity 不满足要求的时候，会重新申请一块两倍的内存，把之前的内容复制过来。在这种情况下，复制的时间复杂度为 $O(n)$。如果不涉及扩容，那么它只修改一个元素的内存，时间复杂度为 $O(1)$。

也就是说，它扩容的时机为，容器大小达到以下时：

1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 …

则每次插入代价设为 $c_i$，则

$$c_i = \begin{cases} i & i 为 2 的幂\\ 1 & others \\ \end{cases}$$

那么则有：

$$\begin{aligned} \sum_{i = 0}^nc_i &\le n + \sum_{j = 0}^{\lfloor log_2n \rfloor}2^j \\ &\le n + 2n\\ &\le 3n \end{aligned}$$

因为共有 $n$ 次插入，所以总时间复杂度为 $O(3n)$，均摊下来平均时间复杂度为 $O(3)$。