std :: vector插入的摊销分析

std :: vector插入的摊销分析

假设您的意思是

push_back

插入而不是插入，我相信重要的部分是乘以某个常数（而不是每次都获取N个以上的元素），并且只要您这样做，您就会得到摊销的常数时间。更改因子会更改平均情况和最坏情况的性能。

具体来说：如果常数因数太大，则平均情况下性能会很好，但最坏情况下的性能会变差，尤其是在阵列变大时。例如，假设仅将第10001个元素推入其中，就将10000大小的向量加倍（2x）。编辑：正如迈克尔·伯尔（Michael
Burr）间接指出的那样，这里的实际成本可能是您将增加的内存远远超出您的需要。我要补充一点的是，如果您的因素太大，则会有一些影响速度的缓存问题。可以肯定地说，如果您增长的比实际需要的多得多，则存在实际成本（内存和计算）。

但是，如果您的常数因子太小，比如说（1.1x），那么您将具有最坏情况下的性能，但平均性能不佳，因为您将不得不承担重新分配太多次的成本。

另外，请参阅Jon Skeet先前对类似问题的回答 （感谢@Bo Persson）

有关分析的更多信息：假设您有

n

要退回的项目，并且乘数为

M

。这样，重新分配的数量将大致

M

为

n

（

log_M(n)

）的对数。第三

i

次重新分配的成本将与

M^i

（

M

与

i

次幂）成比例。则所有回退的总时间为

M^1+ M^2 + ...M^(log_M(n))

。推回次数为

n

，因此，您得到的该级数（这是一个几何级数，并减少到大致

(nM)/(M-1)

极限）除以

n

。这大致是一个常数

M/(M-1)

。

对于较大的价值，

M

您将超支很多，并分配超出正常需要的数量（我在上面提到）。对于较小的值

M

（接近1），此常数

M/(M-1)

变大。该因素直接影响平均时间。