Какая сложность получения элемента set?

Временная сложность получения элемента из Set

Получение элемента из множества (set) в Python имеет очень хорошую временную сложность — в среднем O(1).

Основные операции

Проверка наличия элемента: O(1) в среднем

s = {1, 2, 3, 4, 5}
if 10 in s:  # O(1) в среднем случае
    print("Found")

Добавление элемента: O(1) в среднем

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

Удаление элемента: O(1) в среднем

s.remove(3)  # O(1) в среднем
s.discard(3)  # O(1) в среднем

Итерация по set: O(n)

for element in s:  # O(n) — нужно пройти по всем элементам
    print(element)

Почему O(1)?

Set реализован как хеш-таблица (hash table). Операция работает так:

1. Вычисляется хеш элемента: hash(element)
2. Хеш используется как индекс в массиве
3. Элемент проверяется за O(1) в среднем

Практическое сравнение: Set vs List

import time

s = set(range(1000000))
lst = list(range(1000000))

# Set lookup
start = time.time()
for _ in range(100000):
    _ = 500000 in s  # O(1)
print(f"Set: {time.time() - start:.4f}s")

# List lookup
start = time.time()
for _ in range(100000):
    _ = 500000 in lst  # O(n)
print(f"List: {time.time() - start:.4f}s")

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

Хотя редко, в худшем случае при коллизиях хешей может быть O(n). Python обычно избегает этого с динамическим расширением таблицы.

Операции с множествами

s1 = {1, 2, 3, 4}
s2 = {3, 4, 5, 6}

union = s1 | s2  # O(len(s1) + len(s2))
intersection = s1 & s2  # O(min(len(s1), len(s2)))
difference = s1 - s2  # O(len(s1))

Примеры использования

Удаление дубликатов: O(n)

data = [1, 2, 2, 3, 3, 3, 4]
unique = list(set(data))

Проверка уникальности: O(n)

def has_duplicates(data):
    seen = set()
    for element in data:
        if element in seen:  # O(1)
            return True
        seen.add(element)  # O(1)
    return False

Поиск общих элементов: O(min(n, m))

def find_common(arr1, arr2):
    return set(arr1) & set(arr2)

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

Ключевые выводы

• Set O(1) для проверки наличия элемента
• List O(n) для проверки наличия элемента
• Для работы с большими данными и частыми проверками используй set
• Set идеален для удаления дубликатов и работы с уникальными значениями
• Худший случай O(n) редко случается в практике