← Все вопросы
Почему словарь и множество дают O(1), и когда это ломается?
16
Все говорят, что доступ к dict и проверка x in set — это O(1). Но ведь под капотом хеш-таблица, а коллизии бывают. В каких ситуациях это перестаёт быть O(1) и проседает до O(n)?
3 ответа
23
✓ Принятый ответ — помог автору
O(1) у dict/set — это амортизированная средняя сложность. Хеш-функция переводит ключ в индекс в массиве, и в большинстве случаев попадаешь сразу.
Когда ломается до O(n):
- Массовые коллизии — если хеши многих ключей совпадают, они складываются в одну «корзину», и поиск превращается в перебор. На практике с нормальными встроенными типами этого почти не бывает, но в специально подобранных данных (hash flooding) — реально.
- Рехеширование — когда таблица заполняется, она перестраивается в больший массив. Одна такая операция дорогая, но «размазывается» по многим вставкам, поэтому в среднем всё ещё O(1).
Итого: на практике с обычными ключами (числа, строки) можешь смело считать O(1). Гарантии в худшем случае нет, но в реальных задачах она почти всегда выполняется.
Александра Захарова Ещё момент: ключом может быть только хешируемый (неизменяемый) объект — список туда не положишь. · 17 месяцев назад
10
В среднем O(1), в худшем (полные коллизии) O(n). На обычных данных худший случай практически не встречается.
-4
O(1) всегда, это же хеш-таблица.
Юлия Зайцева Не всегда — в худшем случае при коллизиях O(n). Просто на практике редко. · 17 месяцев назад
Ваш ответ
Войдите, чтобы ответить на вопрос.
