Aká je asymptotická zložitosť operácií s triedou std::vector v C++?

Asymptotická zložitosť hlavných operácií s std::vector:

Operácia	Priemerný čas	Najhorší čas
Prístup k prvku ([], at)	O(1)	O(1)
Vkladanie/odstraňovanie na konci	O(1)	O(N)
Vkladanie/odstraňovanie na začiatku/stred	O(N)	O(N)
Získanie veľkosti (size)	O(1)	O(1)
Zmena veľkosti (resize)	O(N)	O(N)

Vysvetlenie:

• O(1) (konštantný čas): Operácia sa vykoná v pevnom počte krokov, nezávisle od veľkosti poľa.
• O(N) (lineárny čas): Čas vykonania operácie je priamo úmerný počtu prvkov v poli (N).

Ďalej:

• Vkladanie/odstraňovanie na konci môže v najhoršom prípade vyžadovať O(N) kvôli presunu pamäte (realloc), keď aktuálna kapacita nestačí. Pri realloc je vytvorený nový väčší buffer a všetky existujúce prvky sú skopírované do neho. Vďaka stratégii alokácie pamäte (zvyčajne zdvojnásobenie kapacity) je priemerný čas vkladania/odstraňovania na konci O(1).
• Vkladanie/odstraňovanie v strede si vyžaduje posunutie všetkých nasledujúcich prvkov, čo trvá O(N) času.

Príklad realloc pri push_back:

// Predpokladajme, že pole má kapacitu 4 a je plné
std::vector<int> vec = {1, 2, 3, 4}; // Kapacita = 4, Veľkosť = 4

// Pridanie nového prvku vyžaduje realloc
vec.push_back(5); // Možno, že kapacita bude 8 a všetky prvky budú skopírované

// Operácia push_back v tomto prípade trvala O(N) času,
// kde N je počet prvkov pred reallocáciou.