Jaka jest złożoność czasowa usuwania elementów z wektora w najgorszym przypadku?

W najgorszym przypadku usuwanie elementów z wektora (std::vector w C++) ma złożoność czasową O(n), gdzie n to liczba elementów w wektorze po pozycji usunięcia. Wynika to z faktu, że po usunięciu elementów wszystkie kolejne elementy muszą zostać przesunięte w lewo, aby wypełnić powstałą lukę.

Na przykład, jeśli usuniemy element na początku wektora, wszystkie pozostałe elementy muszą zostać przesunięte o jedno miejsce do przodu, co wymaga O(n) operacji.

std::vector<int> v = {1, 2, 3, 4, 5};
v.erase(v.begin()); // usunięcie pierwszego elementu
// wszystkie elementy przesuwają się o jedno miejsce w lewo

Jeśli usunięty element znajduje się na końcu, przesuwanie nie jest konieczne, a operacja będzie bliższa O(1). Jednak w najgorszym przypadku — O(n).