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)\)
标签：big,复杂度,back,vector,push,sum From： https://www.cnblogs.com/C111111/p/17613553.html