O (1) взлеты взгляда хеша?
Я натыкался на утверждение, что HashSet <T>.Contains () является O (1) операция. Это удивило меня начиная с каждого обсуждения хеширования, с которым я встретился, упоминает возможность коллизий, потенциально ведя к O (n) время выполнения.
Будучи любопытным, я изучил документацию для HashSet <T>.Contains и также HashTable. Содержит. Документация для обоих методов предъявляет ту же самую претензию.
Когда я смотрю в отражателе, HashSet <T>.Contains () реализован с для цикла, пройдя список слотов, содержащих значения, которые имеют тот же хеш.
Теперь по общему признанию те те же обсуждения хеширования также упомянули, что хороший алгоритм хеширования избегает коллизий, и при тех обстоятельствах поиск действительно будет O (1). Но мое понимание Большой нотации O - то, что это - время времени выполнения худшего случая, не лучше всего.
Так O (1), требуют неправильный? Или я пропускаю что-то?
9 ответов
Но мое представление о нотации Big O таково, что это наихудшее время выполнения, а не лучшее.
К сожалению, не существует «стандарта» для Big-O при описании алгоритмов. Часто он используется для описания общего или среднего случая, но не худшего.
Из Википедии :
... эта нотация теперь часто также используется при анализе алгоритмов для описания использования вычислительных ресурсов алгоритмом: наихудший случай или средний случай ...
В данном случае это описание стандартного случая при правильном хешировании. Если у вас есть правильное хеширование, ограничивающее поведение будет постоянным для размера N, следовательно, O (1).
Для правильно реализованной хеш-таблицы поисковые запросы амортизируют постоянную временную сложность.
На практике, как вы говорите, один поиск может быть O (n) в случае коллизий. Однако, если вы выполняете большое количество поисков, средняя временная сложность одной операции остается постоянной.
Цитата из Википедии:
Амортизированный анализ отличается от среднего случая тем, что вероятность не учитывается; Амортизированный анализ гарантирует время одной операции по сравнению с худшим случаем.
Метод требует знания возможных серий операций. Чаще всего это происходит со структурами данных, состояние которых сохраняется между операциями. Основная идея заключается в том, что операция наихудшего случая может изменить состояние таким образом, что наихудший случай не может повториться в течение длительного времени, таким образом «амортизируя» ее стоимость.
Нет, Big O не определяет "наихудший случай", он определяет предел. Поиск на основе хэша (с хорошими алгоритмами хэширования, которые обеспечивают эффективное распределение значений и низкую частоту коллизий) прогрессирует к постоянному значению по мере увеличения числа элементов (они никогда не достигнут этого постоянного значения, но в этом и смысл того, что это предел).
Нет, нотация Big-O не обязательно ограничивается наихудшим случаем. Обычно вы видите публикацию Big-O для наилучшего, среднего и наихудшего случая. Просто большинство людей склонны сосредотачиваться на худшем случае. За исключением хеш-таблицы, наихудший случай случается редко, поэтому использование среднего случая более полезно.
Да, хорошая хеш-функция снижает вероятность коллизии.Плохая хеш-функция может вызвать эффект кластеризации (когда разные значения хешируются до одного и того же значения или близки к одному и тому же значению). Легко продемонстрировать, что HashSet действительно может стать O (n), реализовав функцию GetHashCode таким образом, чтобы она всегда возвращала одно и то же значение.
В суматохе yes HashSet и Dictionary можно описать как имеющие O (1) сложность выполнения, потому что упор делается на сценарий среднего случая.
Кстати, Big-O можно использовать и для анализа амортизированной сложности. Амортизированная сложность - это то, как последовательность отдельных (а иногда даже разных) операций ведет себя, когда сгруппированы вместе, как если бы они были одной большой операцией. Например, говорят, что расширенное дерево имеет амортизированную сложность поиска, вставки и удаления O (log (n)), хотя в худшем случае для каждого из них может быть O (n), а в лучшем случае - O (1).
Насколько я понимаю, Big Oh заключается в том, что «наихудший случай» обычно связан с количеством задействованных элементов. Итак, если функция должна была выполнить O (n) с 10 элементами, но O (n в квадрате) с 100 или более (не уверен, что такой алгоритм действительно существует), то алгоритм считается O (n в квадрате).
O (1) не обязательно означает «худший случай». Для хешей обычно говорят, что «ожидаемое» время поиска равно O (1), так как вероятность коллизий хешей мала.
Хэш-таблицы не только имеют среднюю производительность O(1), но если хэш-функция случайна, то для любого заданного процента P < 100%, производительность, которую можно получить P% времени от правильно спроектированной хэш-таблицы, равна O(1). Хотя крайние паразитные случаи становятся все более серьезными с увеличением N, это уравновешивается тем, что даже умеренно паразитные случаи становятся все менее вероятными.