Ako je určovaná časová zložitosť operácie vloženia prvku na koniec štandardného vektora v C++?

Časová zložitosť operácie vstupu prvku na koniec štandardného poľa (std::vector) v C++ je zvyčajne amortizovaná konštantná, teda O(1) v priemere. To je spôsobené tým, že pole alokuje pamäť s rezervou, a pri pridávaní prvku, ak aktuálny buffer nie je plný, je vkladanie rýchle — jednoducho sa skopíruje alebo presunie prvok.

Avšak, keď je vnútorný buffer poľa plný, dochádza k prealokácii pamäti: alokuje sa nový buffer väčšej veľkosti (zvyčajne dvojnásobnej), všetky prvky sa skopírujú alebo presunú do nového bufferu a starý sa uvoľní. Táto operácia trvá čas O(n), kde n je aktuálny počet prvkov.

Keďže takéto prealokácie sa neudejú pri každom vklade, ale iba periodicky, amortizovaná zložitosť vkladania na koniec zostáva O(1).

Príklad:

std::vector<int> v;
for (int i = 0; i < 1000; ++i) {
    v.push_back(i); // amortizované O(1)
}