Mi a legrosszabb esetben a vektor elemeinek törlésének időbeli komplexitása?

A legrosszabb esetben egy vektor (std::vector C++-ban) elemeinek eltávolítása időkomplexitása O(n), ahol n az eltávolítás utáni elemek száma a vektorban. Ez azért van, mert az elemek eltávolítása után minden következő elemet balra kell mozgatni, hogy kitöltse az üres helyet.

Például, ha a vektor elejéről törlünk egy elemet, akkor az összes többi elemet egy pozícióval előrébb kell mozgatni, ami O(n) műveletet igényel.

std::vector<int> v = {1, 2, 3, 4, 5};
v.erase(v.begin()); // az első elem eltávolítása
// minden elem egy pozícióval balra mozog

Ha a végén lévő elemet töröljük, akkor nem szükséges mozgatni, és az művelet közelebb lesz az O(1)-hez. De a legrosszabb esetben — O(n).