Какая сложность у метода pop

Метод pop() в Python имеет разную временную сложность в зависимости от типа данных:

1. Списки (list):
   pop() без аргументов (удаление последнего элемента) — O(1).
   pop(i) с указанием индекса — O(n), так как требует сдвига всех элементов после i.

2. Множества (set) и словари (dict):
   pop() — O(1) в среднем случае, но O(n) в худшем (из-за возможных коллизий хеш-таблицы).

Пример для списка:

lst = [1, 2, 3, 4]
lst.pop()    # O(1) → удаляет 4
lst.pop(0)   # O(n) → удаляет 1, сдвигает остальные

Пример для множества:

s = {1, 2, 3}
s.pop()  # O(1) → удаляет случайный элемент

Для deque из collections popleft() и pop() — O(1).