Quelle est la complexité temporelle de la suppression d'éléments d'un vecteur dans le pire cas?

Dans le pire cas, la suppression d'éléments d'un vecteur (std::vector en C++) a une complexité temporelle de O(n), où n est le nombre d'éléments dans le vecteur après la position de suppression. Cela est dû au fait qu'après la suppression d'éléments, tous les éléments suivants doivent être décalés vers la gauche pour combler l'espace vide.

Par exemple, si un élément est supprimé au début du vecteur, tous les autres éléments doivent être décalés d'une position vers l'avant, ce qui nécessite O(n) opérations.

std::vector<int> v = {1, 2, 3, 4, 5};
v.erase(v.begin()); // suppression du premier élément
// tous les éléments sont décalés d'une position vers la gauche

Si un élément est supprimé à la fin, aucun décalage n'est nécessaire, et l'opération sera plus proche de O(1). Mais dans le pire cas — O(n).