Care este complexitatea asimptotică a operațiilor cu clasa std::vector în C++?

Complexitatea asimptotică pentru operațiile principale cu std::vector:

Operație	Timp mediu	Timp cel mai rău
Acces la element ([], at)	O(1)	O(1)
Inserare/ștergere la sfârșit	O(1)	O(N)
Inserare/ștergere la început/mijloc	O(N)	O(N)
Obținerea dimensiunii (size)	O(1)	O(1)
Schimbarea dimensiunii (resize)	O(N)	O(N)

Explicații:

• O(1) (timp constant): Operația se realizează într-un număr fix de pași, indiferent de dimensiunea vectorului.
• O(N) (timp liniar): Timpul de execuție al operației este proporțional cu numărul de elemente din vector (N).

În plus:

• Inserarea/ștergerea la sfârșit poate necesita O(N) în cel mai rău caz din cauza realocării memoriei, atunci când capacitatea curentă nu este suficientă. La realocare, se creează un nou buffer mai mare și toate elementele existente sunt copiate în el. Datorită strategiei de alocare a memoriei (de obicei, dublarea capacității), timpul mediu pentru inserare/ștergere la sfârșit este O(1).
• Inserarea/ștergerea în mijloc necesită deplasarea tuturor elementelor următoare, ceea ce durează O(N) timp.

Exemplu de realocare la push_back:

// Să presupunem că vectorul are o capacitate de 4 și este plin
std::vector<int> vec = {1, 2, 3, 4}; // Capacitate = 4, Dimensiune = 4

// Adăugarea unui nou element necesită realocare
vec.push_back(5); // Poate ca capacitatea să devină 8, iar toate elementele sunt copiate

// Operația push_back în acest caz a durat O(N) timp,
// unde N este numărul de elemente înainte de realocare.