Чӣ тавр муайян карда мешавад мураккабии вақти амалиёти ворид кардани унсур ба охири вектории стандартӣ дар C++?

C++-да стандарт вектор (std::vector) охиргига элемент қўшиш операциясининг вақт мураккаблиги одатда амортизмланган мос келади, яъни O(1) ўртача. Бу, вектор ёдлашни резервлаш билан ажратиб қўйганлиги ва элемент қўшилганда, агар ҳозирги буфер тўлмаган бўлса, қўшиш тез бўлишини — элементни фақат кўчириш ёки кўчиришни ўзгартиришни талаб қилади.

Бироқ, агар векторнинг ички буфери тўлса, ёдлаш қайта ташкил этилади: катталиги икки баробар бўлган янги буфер ажратилади, барча элементлар янги буферга кўчирилади ёки кўчирилади ва эскиси озод қилинади. Бу операция вақт талаб қилади O(n), бу ерда n ҳозирги элементлар сони.

Бундай қайта ташкил этишлар ҳар бир қўшишда бўлмайди, балки фақат перидик равишда юз беради, шунинг учун амортизмланган қўшиш мураккаблиги O(1) бўлиб қолади.

Масалан:

std::vector<int> v;
for (int i = 0; i < 1000; ++i) {
    v.push_back(i); // амортизмланган O(1)
}