Kāda ir elementu dzēšanas no vektora laika sarežģītība sliktākajā gadījumā?

Vis sliktākajā gadījumā, no vektora (C++ std::vector) elementu dzēšana ir laika sarežģītība O(n), kur n ir elementu skaits pēc dzēšanas pozīcijas. Tas ir tāpēc, ka pēc elementu dzēšanas visi sekojošie elementi ir jāpārvieto pa kreisi, lai aizpildītu radušos brīvo vietu.

Piemēram, ja dzēšam elementu vektora sākumā, visi pārējie elementi ir jāpārvieto par vienu pozīciju uz priekšu, kas prasa O(n) operācijas.

std::vector<int> v = {1, 2, 3, 4, 5};
v.erase(v.begin()); // dzēst pirmo elementu
// visi elementi tiek pārvietoti par vienu pozīciju uz priekšu

Ja dzēšam elementu no beigām, pārvietošana nav nepieciešama, un operācija būs tuvāk O(1). Bet sliktākajā gadījumā — O(n).