std::vector.push_back()
使用push_back()函数时，在不用扩增容量的情况下，时间复杂度是O(1)；
但如果需要扩增容量，会将旧vector中所有元素复制到新的内存空间中，时间复杂度是O(n)。
(资料图片)
假定扩增后的容量为原来的m倍
假如从一个空vevtor开始，需要插入n次元素，下面推导其时间复杂度：
对于第i次插入，其时间代价为：
\[c_i=\begin{cases}i,~i-1是m的幂\\1,~其他情况\end{cases}\]则总代价为：
\[\sum_{i=1}^{n}c_i~=~\sum_{j=0}^km^j+\big(n-(k+1)\big),~~~~~~k = \log_mn向下取整\]其中复制的次数为k+1（第一次插入从空vector开始也需要扩增，但不需要复制元素，复杂度为1），
\(\sum_{j=0}^km^j\) 为复制所需要的总时间代价，\(\big(n-(k+1)\big)\) 为不用复制的插入所需要的总时间代价。
有以下推导：
\[\sum_{j=0}^km^j~=~m^0+m^1+...+m^k~=~m^{k+1}-1~\leq~m^{k+1}\tag{1}\\\]\[m^{k+1}~=~m^k\cdot m\]\[m^k~=~m^{log_m~n}~=~n\tag{2}\]即：
\[\sum_{j=0}^km^j~\leq~n\cdot m\]又有 \(\big(n-(k+1)\big)~\leq~n\) ，所以：
\[\sum_{i=1}^{n}c_i~\leq~n~+~n\cdot m\]即时间复杂度约为 \(O(n~+~n\cdot m)\) ，其中m为扩增容量的倍数。
所以从空vector开始使用push_back()插入若干个元素的平均时间复杂度为 \(O(m)\)
