Какая алгоритмическая сложность удаления объекта в списке в Python

Удаление объекта из списка в Python с помощью list.remove() или del list[index] имеет линейную сложность O(n), так как требует поиска элемента и сдвига всех последующих элементов.

Пример:

my_list = [1, 2, 3, 4, 5]
my_list.remove(3)  # O(n) - поиск и удаление
del my_list[1]     # O(n) - сдвиг элементов после индекса 1

Если индекс известен и нужно удалить последний элемент (list.pop() без аргументов), сложность O(1), так как не требуется сдвиг элементов.

Для частых удалений лучше использовать другие структуры данных:

• collections.deque для удаления с обоих концов (O(1))
• Множества (set) для быстрого удаления по значению (O(1) в среднем случае)