Jaká je časová složitost operace odstranění prvků z vektoru v nejhorším případě?

V nejhorším případě má odstranění prvků z vektoru (std::vector v C++) časovou složitost O(n), kde n je počet prvků vektor po pozici odstranění. To je způsobeno tím, že po odstranění prvků je třeba všechny následující prvky posunout vlevo, aby se zaplnil vzniklý volný prostor.

Například, pokud odstraníme prvek na začátku vektoru, všechny ostatní prvky je třeba posunout o jedno místo vpřed, což vyžaduje O(n) operací.

std::vector<int> v = {1, 2, 3, 4, 5};
v.erase(v.begin()); // odstranění prvního prvku
// všechny prvky se posunou o jedno místo vlevo

Pokud je odstraněn prvek na konci, není třeba posunovat, a operace bude blíže k O(1). Ale v nejhorším případě — O(n).