Koja je vremenska složenost operacije brisanja elemenata iz vektora u najgorem slučaju?

У најгорем случају, уклањање елемената из вектора (std::vector у C++) има временску сложеност O(n), где n представља број елемената у вектору након позиције уклањања. То је због тога што након уклањања елемената, сви следећи елементи морају бити померени улево да попуне насталу празнину.

На пример, ако уклонимо елемент на почетку вектора, сви остали елементи морају бити померени за једну позицију напред, што захтева O(n) операција.

std::vector<int> v = {1, 2, 3, 4, 5};
v.erase(v.begin()); // уклањање првог елемента
// сви елементи се померају за једну позицију улево

Ако се уклони елемент на крају, померање није потребно, и операција ће бити ближа O(1). Али у најгорем случају — O(n).