Какова временная сложность операции удаления элементов из вектора в худшем случае?

В худшем случае удаление элементов из вектора (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).