vector push_back函数时间复杂度的证明

前言

对于 std::vector 的 push_back 函数， cplusplus.com 上的复杂度解释如下:

Constant (amortized time, reallocation may happen).
常数 (均摊时间，可能发生重新分配)

它的原理想必大家都知道，当大小达到容量之后，为了保证内存的连续性，就会再开一个新的内存块，把之前的复制过去。

每次复制时间复杂度为 (O(n)), 直觉上，每次 push_back 的时间复杂度不太像 (O(1)), 但由于只有很少的情况下才会复制，所以均摊时间确实很快，但至于为什么是 (O(1)), 本篇文章将给出证明。

聚能分析

此代码打印 push_back (1 imes 10 ^ 5) 个元素时 vector 的容量大小变化:

#include <iostream>
#include <vector>
int main() {
	std::vector<int> v;
	int last = 0;
	for (int i = 1; i <= 1e5; i++) {
		v.push_back(1);
		if (last != (int)v.capacity()) {
			std::cout << v.capacity() << " ";
			last = v.capacity();
		}
	}
}

实际运行时，会输出 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072

很明显都是2的次幂, 所以，每次插入代价

[c_i=left{ egin{aligned} i && i - 1 ext{为} 2 ext{的幂} \ 1 && ext{其他情况} end{aligned} ight. ]

则

[sum_{i=1}^n c_i le n + sum_{j=0}^{lfloor lg n floor} 2^j < n + 2n = 3n ]

共有 (n) 次插入操作，总时间复杂度为 (O(3n)), 单次均摊时间复杂度为 (O(3)) 。

核算法

考虑每次 push_back 要产生的代价，可能不一样，有的时候只需要付出插入1个元素的1代价，有的时候却要付出复制n个元素的n代价，我们只要在每次插入元素的时候提前付出代价，为之后可能的复制元素做好准备。复制元素的时候用之前存储的代价支付，就相当于每次插入元素代价相同。

那么每次插入元素都要付出什么代价呢？

插入元素本身的1代价，不做解释。
为将来复制这个元素付出的1代价。因为移动一个元素要付出1代价，而如果这1代价在插入的时候就已经支付，那么移动的时候就不用付出额外代价
为已经复制过的元素将来再次复制所付出的代价。如果仅仅为自己的复制付出代价，那么之前复制过来的元素已经消耗了自己插入时付出的代价，它们将无法复制，所以必须要再为它们付出1次代价

此图画出了2次复制，下标为3的元素，要为自己的插入，将来自己的复制和将来下标为1的元素的复制付出3次代价。

同理，下标为4的元素，要为自己的插入，将来自己的复制和将来下标为2的元素的复制付出3次代价。

这是第1次复制，第二次复制的时候，下标为1， 2， 3， 4的元素又有5， 6， 7， 8为它们付出代价。

所以每次插入元素付出了3次代价，均摊时间复杂度为(O(3))。

还有需要注意的一点，如果插入了几个元素但还没有复制的时候，还存储着一些没有被消耗的代价，此时总时间是小于 (3n) 的，只有刚完成一次复制时，时间才是 (3n), 同时，存储的代价也为0。所以有：当前总时间 = 均摊总时间 - 存储的代价

其他

但是由于STL自带大常数，不开启 (O2) 优化的情况下， (vector) 插入的时间是数组的 6.5 倍左右，开启 (O2) 优化的情况下， (vector) 插入的时间是数组的 2.5 倍左右, 较接近 (O(3)) 。