Vektor elementlərinin silinməsi əməliyyatının ən pis halda vaxt mürəkkəbliyi nədir?

Ən pis halda, C++-da std::vector elementlərinin silinməsi vaxt mürəkkəbliyi O(n)-dir, burada n silinmə mövqeyindən sonra vektorun element sayıdı. Bu, elementləri siləndən sonra bütün sonrakı elementlərin sola doğru hərəkət etdirməsini tələb edir.

Məsələn, vektorun başlanğıcındakı elementi silsək, digər bütün elementlər bir mövqe irəli hərəkət etdirməlidir, bu da O(n) əməliyyat tələb edir.

std::vector<int> v = {1, 2, 3, 4, 5};
v.erase(v.begin()); // ilk elementi silmək
// bütün elementlər bir mövqe sola hərəkət edir

Əgər sonuncu element silinsə, hərəkət etdirməyə ehtiyac yoxdur və əməliyyat O(1)-ə daha yaxın olacaq. Amma ən pis halda — O(n).