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

Сложность метода pop() в Python

Сложность метода pop() зависит от типа структуры данных и параметров вызова. Рассмотрю все варианты.

1. pop() на списке (list)

По умолчанию (удаление последнего элемента):

my_list = [1, 2, 3, 4, 5]
value = my_list.pop()  # Удаляет 5
print(my_list)  # [1, 2, 3, 4]

Сложность: O(1)

Удаление последнего элемента не требует сдвига остальных элементов.

# На 1000000 элементов — практически мгновенно
big_list = list(range(1000000))
big_list.pop()  # Быстро!

По индексу (удаление произвольного элемента):

my_list = [1, 2, 3, 4, 5]
value = my_list.pop(1)  # Удаляет элемент с индексом 1 (значение 2)
print(my_list)  # [1, 3, 4, 5]

Сложность: O(n), где n — количество элементов после удаляемого

Причина: после удаления элемента все следующие элементы сдвигаются на одну позицию влево:

# Худший случай — удаление первого элемента
my_list = list(range(1000000))
my_list.pop(0)  # Медленно! Сдвигает 999999 элементов

# Лучший случай — удаление последнего
my_list.pop()  # Быстро! Ничего не сдвигается

# Средний случай — середина
my_list.pop(len(my_list) // 2)  # O(n/2) = O(n)

2. pop() на словаре (dict)

my_dict = {\"a\": 1, \"b\": 2, \"c\": 3}
value = my_dict.pop(\"a\")  # Удаляет ключ a
print(my_dict)  # {b: 2, c: 3}

# pop с значением по умолчанию
value = my_dict.pop(\"z\", None)  # Возвращает None, если ключа нет

Сложность: O(1) в среднем

Потому что словарь использует хеширование, удаление — это просто удаление из хеш-таблицы:

# Даже на миллионе элементов
big_dict = {i: i*2 for i in range(1000000)}
big_dict.pop(500000)  # Практически O(1)

3. pop() на множестве (set)

my_set = {1, 2, 3, 4, 5}
value = my_set.pop()  # Удаляет произвольный элемент
print(my_set)  # {2, 3, 4, 5} (порядок может отличаться)

Сложность: O(1) в среднем

Множество тоже использует хеширование:

big_set = set(range(1000000))
value = big_set.pop()  # Быстро!

4. pop() на очереди (collections.deque)

from collections import deque

my_deque = deque([1, 2, 3, 4, 5])
value = my_deque.pop()  # Удаляет из конца
print(my_deque)  # deque([1, 2, 3, 4])

value = my_deque.popleft()  # Удаляет из начала
print(my_deque)  # deque([2, 3, 4])

Сложность: O(1) для обоих операций

deque оптимизирован для удаления с обоих концов:

# Оба быстрые
big_deque = deque(range(1000000))
big_deque.pop()      # O(1)
big_deque.popleft()  # O(1)

5. Таблица сложностей

6. Практические примеры и производительность

Быстрое удаление:

import time

# Список: удаление с конца O(1)
my_list = list(range(100000))
start = time.time()
for _ in range(100000):
    my_list.pop()  # Быстро
print(f\"list.pop(): {time.time() - start:.4f}s\")

# Словарь: удаление по ключу O(1)
my_dict = {i: i for i in range(100000)}
start = time.time()
for i in range(100000):
    my_dict.pop(i, None)  # Быстро
print(f\"dict.pop(): {time.time() - start:.4f}s\")

Медленное удаление:

import time

# Список: удаление из начала O(n)
my_list = list(range(100000))
start = time.time()
for _ in range(100):
    my_list.pop(0)  # Медленно!
print(f\"list.pop(0): {time.time() - start:.4f}s\")

# Деке: вместо списка
from collections import deque
my_deque = deque(range(100000))
start = time.time()
for _ in range(100):
    my_deque.popleft()  # Быстро!
print(f\"deque.popleft(): {time.time() - start:.4f}s\")

7. Когда это критично

Проблема — частое удаление из начала списка:

# Неправильно: O(n) на каждую операцию
queue = list(range(10000))
for _ in range(1000):
    queue.pop(0)  # Медленно!
# Общая сложность: O(n * m)

Правильно — использовать deque:

from collections import deque

# Правильно: O(1) на каждую операцию
queue = deque(range(10000))
for _ in range(1000):
    queue.popleft()  # Быстро!
# Общая сложность: O(m)

Проблема в Stack с использованием списка:

# Неправильно, но обычно OK (pop с конца)
stack = [1, 2, 3, 4, 5]
while stack:
    value = stack.pop()  # O(1) — OK

8. Выводы

Запомни:

• list.pop() (с конца) = O(1), list.pop(0) (с начала) = O(n)
• dict.pop(key) = O(1)
• set.pop() = O(1)
• deque.pop() и deque.popleft() = O(1)

Практический совет: Если часто удаляешь элементы с начала последовательности, используй deque вместо list. Это избавит от O(n) копирования элементов!