Jak określana jest złożoność czasowa operacji wstawiania elementu na koniec standardowego wektora w C++?

Złożoność czasowa operacji wstawiania elementu na koniec standardowego wektora (std::vector) w C++ jest zazwyczaj amortyzowana do stałej, czyli O(1) w średnim przypadku. Wynika to z faktu, że wektor rezerwuje pamięć z zapasem, a podczas dodawania elementu, jeśli bieżący bufor nie jest pełny, wstawianie odbywa się szybko — element jest po prostu kopiowany lub przenoszony.

Jednak gdy wewnętrzny bufor wektora jest pełny, dochodzi do rezerwacji nowej pamięci: alokowany jest nowy bufor większego rozmiaru (zwykle dwukrotnie większy), wszystkie elementy są kopiowane lub przenoszone do nowego bufora, a stary jest zwalniany. Operacja ta zajmuje czas O(n), gdzie n to aktualna liczba elementów.

Ponieważ takie rezerwacje nie zachodzą przy każdej operacji wstawiania, a tylko okresowo, amortyzowana złożoność wstawiania na koniec pozostaje O(1).

Przykład:

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