Kokia yra elementų ištrynimo iš vektoriaus laiko sudėtingumas blogiausiu atveju?

Blogiausiu atveju, elementų ištrynimas iš vektoriaus (C++ std::vector) turi laiko sudėtingumą O(n), kur n yra elementų skaičius po ištrynimo pozicijos. Tai yra todėl, kad po elementų ištrynimo visi vėlesni elementai turi būti perkelti į kairę, kad užpildytų atsiradusią tuštumą.

Pavyzdžiui, jei ištrinsime elementą pradžioje, visi kiti elementai turi būti perkelti vieną poziciją į priekį, tai reikalauja O(n) operacijų.

std::vector<int> v = {1, 2, 3, 4, 5};
v.erase(v.begin()); // ištrinti pirmą elementą
// visi elementai perkelti viena pozicija į kairę

Jei ištrinsime paskutinį elementą, perkėlimas nereikalingas, ir operacija bus arčiau O(1). Bet blogiausiu atveju — O(n).