Какая алгоритмическая сложность вставки в множестве в Python?

Алгоритмическая сложность вставки в set в Python

Ответ

Вставка в set в Python имеет сложность O(1) в среднем случае (average case).

Почему O(1)?

set в Python — это хеш-таблица (hash table). Вот как работает вставка:

s = {1, 2, 3}
s.add(4)  # O(1) в среднем

# Что происходит внутри:
# 1. Вычисляется hash(4) → целое число
# 2. hash(4) % len(table) → индекс в таблице
# 3. Элемент помещается в эту ячейку

В идеальном случае каждый элемент попадает в пустую ячейку, и вставка — это O(1).

Худший случай: O(n)

Но важно знать про худший случай:

# Худший случай — когда много элементов хешируются в один индекс
# Это редко, но возможно при:
# 1. Плохой hash-функции
# 2.攻击(denial of service attack)
# 3. Специально подобранных значениях

class BadHash:
    def __init__(self, value):
        self.value = value
    
    def __hash__(self):
        return 0  # Всегда один и тот же hash!
    
    def __eq__(self, other):
        return self.value == other.value

# Теперь вставка может быть O(n)
s = set()
for i in range(1000):
    s.add(BadHash(i))  # Деградирует в O(n)

Внутри Python

Если копнуть в CPython исходный код, set это фактически словарь без значений:

// Упрощённо из setobject.c
static int
set_add_entry(PySetObject *so, PyObject *key)
{
    // 1. hash_value = PyObject_Hash(key);
    // 2. index = hash_value & (so->mask);  // быстро вычисляет индекс
    // 3. entry = &so->table[index];
    // 4. if (entry is empty) { insert; return 0; }
    // 5. else { handle collision; }
}

Сравнение со списком

# SET — O(1)
my_set = {1, 2, 3}
my_set.add(4)  # O(1) в среднем ✓
if 4 in my_set:  # O(1) в среднем ✓
    pass

# LIST — O(n)
my_list = [1, 2, 3]
my_list.append(4)  # O(1) только в конце списка
if 4 in my_list:  # O(n) — линейный поиск
    pass

Это главное отличие set от list: проверка принадлежности O(1) vs O(n).

Сравнение SET, DICT и LIST

import time

# Вставка
n = 1_000_000

# SET: O(1)
start = time.time()
s = set()
for i in range(n):
    s.add(i)
print(f"Set add: {time.time() - start:.4f}s")  # ~0.05s

# LIST: O(1) амортизированная
start = time.time()
l = []
for i in range(n):
    l.append(i)  # O(1) в конце
print(f"List append: {time.time() - start:.4f}s")  # ~0.02s (даже быстрее!)

# LIST с insert в начало: O(n)
start = time.time()
l = []
for i in range(n):
    l.insert(0, i)  # O(n) — сдвигает все элементы!
print(f"List insert(0): {time.time() - start:.4f}s")  # ~20s (очень медленно!)

Проверка принадлежности

# SET: O(1)
if 999999 in my_set:  # быстро
    pass

# LIST: O(n)
if 999999 in my_list:  # медленно, ищет элемент с конца
    pass

# Пример из жизни
import time

my_set = set(range(1_000_000))
my_list = list(range(1_000_000))

start = time.time()
for _ in range(100):
    if 999999 in my_set:  # O(1) * 100
        pass
print(f"Set membership: {time.time() - start:.6f}s")  # ~0.0001s

start = time.time()
for _ in range(100):
    if 999999 in my_list:  # O(n) * 100
        pass
print(f"List membership: {time.time() - start:.6f}s")  # ~3s (в 30000 раз медленнее!)

Когда использовать SET

# ✅ Проверка наличия элемента
unique_ids = {1, 2, 3, 4, 5}
if user_id in unique_ids:  # O(1)
    process(user_id)

# ✅ Удаление дубликатов
users = [User(1), User(2), User(1), User(3)]
unique_users = set(users)  # O(n)

# ✅ Операции с множествами
set_a = {1, 2, 3}
set_b = {2, 3, 4}
intersection = set_a & set_b  # {2, 3}
union = set_a | set_b  # {1, 2, 3, 4}
difference = set_a - set_b  # {1}

# ❌ Сохранение порядка элементов
# set не гарантирует порядок (хотя в Python 3.7+ он сохраняется как деталь реализации)
my_set = {3, 1, 2}
print(list(my_set))  # порядок непредсказуем

# ✅ Если нужен порядок — используй список или collections.OrderedDict
from collections import OrderedDict
od = OrderedDict()
od[3] = True
od[1] = True
od[2] = True
print(list(od.keys()))  # [3, 1, 2]

Пространственная сложность

# SET требует больше памяти, чем LIST с теми же элементами
# Потому что set хранит таблицу хешей и часто имеет "пустые" ячейки

import sys

my_list = list(range(10000))
my_set = set(range(10000))

print(f"List size: {sys.getsizeof(my_list) / 1024:.2f} KB")  # ~78 KB
print(f"Set size: {sys.getsizeof(my_set) / 1024:.2f} KB")   # ~219 KB (в 2.8 раза больше)

Итоговая таблица

(*амортизированная сложность)

Ответ на вопрос

Вставка в set — O(1) в среднем случае благодаря хеш-таблице. Это главное преимущество set перед list для проверки принадлежности и удаления элементов. Но помните про худший случай O(n) и потребление памяти, которое в 2-3 раза больше, чем у list.