我遇到了thins 网站,其中指出STL向量背面的插入可以是O(1)或O(n).我相信最后的插入应该是向量的O(1).任何人都可以澄清这一点并告诉我作者对O(n)的意思.作者指出,在背面插入STL矢量Back: O(1) or O(n).哪一个 ？
Jer*_*fin 11
复杂性需要摊销不变.
这意味着并非每次插入都需要相同的时间长度,但从长远来看,无论收集的大小如何,它都会平均为常数.
它通过在当前块变满时分配更大的块,并将数据从当前块复制到新块来实现."技巧"是块大小以几何级数增加,因此随着集合变大,副本逐渐减少.
如果你想要足够严重,你实际上可以使时间保持不变,而不仅仅是摊销不变.当你需要分配一个更大的块时,你需要分配一个比旧块大两倍的新块,将新项插入新块中的正确位置,并将一个项从旧块复制到新块.每次插入一个项目时,您都会从旧块中再复制一个项目到新块.每次插入都需要插入一个新项目并复制一个旧项目,因此复杂性将是不变的.
但这会有几个缺点.首先,它显然会保留旧块和新块,而不是在分配新块之后立即释放旧块(几乎).其次,它会丢失时间局部性,因此当它将一个项目从旧块复制到新块时,很可能它不会在缓存中.通过一次性将整个旧块复制到新块,可以获得更好的缓存利用率(至少作为规则).