vector | push_back()的时间复杂度

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)\)

关键词：