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

В худшем случае операция удаления элемента из списка (например, std::vector в C++) имеет временную сложность O(n). Это связано с тем, что после удаления элемента все последующие элементы нужно сдвинуть на одну позицию влево, чтобы заполнить образовавшуюся пустоту.

Для связных списков (например, std::list) удаление элемента по итератору происходит за O(1), так как не требуется сдвигать элементы, но поиск элемента для удаления может занять O(n, если итератор не известен заранее).

Пример для std::vector:

std::vector<int> v = {1, 2, 3, 4, 5};
v.erase(v.begin() + 2); // удаляем элемент с индексом 2
// После удаления элементы с индексами 3 и 4 сдвигаются влево

Таким образом, в худшем случае удаление из динамического массива — O(n).