C++：vector的push_back时间复杂度分析
引导示例
#include <iostream>
#include <vector>
int main() {
std::vector<int> v;
std::cout << v.capacity() << " ";
int last = 0;
for (int i = 1; i <= 10; i++) {
v.push_back(1);
std::cout << v.capacity() << " ";
}
return 0;
}
我们在C++17下运行上面的代码，可以得到如下的结果：
0 1 2 4 4 8 8 8 8 16 16
初步观察到，当进行push_back时，如果容器的大小达到容量，就会再开辟一个新的内存。
复杂度分析：
假设容量从 1 开始，逐步倍增到 2, 4, 8, …, 2^k；总共进行n次插入。
每次扩容的代价为：
总的扩容代价：(求和公式)
加上n次插入：
总的代价为 (3n-1) / n = O(3) = O(1)