O (1) хэш смотрит вверх?

Question

Я столкнулся с утверждением, что HashSet .Contains () является операцией O (1).Это удивило меня, так как в каждом обсуждении хэширования, с которым я сталкивался, упоминалась возможность коллизий, потенциально приводящих к времени выполнения O (n).

Из любопытства я изучил документацию по HashSet . Содержит иHashTable.Contains.Документация для обоих методов имеет одно и то же утверждение.

Когда я смотрю в отражатель, HashSet .Contains () реализуется с помощью цикла for, просматривая список слотов, содержащих значения, имеющие одинаковый хэш.

Теперь, по общему признанию, те же самые обсуждения хеширования также упоминали, что хороший алгоритм хеширования избегает коллизий, и при этих обстоятельствах поиск действительно будет O (1).Но мое понимание нотации Big O состоит в том, что это время выполнения в худшем случае, а не в лучшем случае.

Так что утверждение O (1) неверно?Или я что-то упустил?

Answer 1

Но мое понимание нотации Big O состоит в том, что это время выполнения наихудшего случая, а не лучшее.

К сожалению, не существует "стандарта" для Big-O при описании алгоритмов,Часто он используется для описания общего или среднего случая, а не худшего.

Из Википедии :

... эта запись теперь часто также используется при анализе алгоритмов для описания использования алгоритмом вычислительных ресурсов: худшеерегистр или средний регистр ...

В данном случае он описывает стандартный случай при условии правильного хеширования.Если у вас есть правильное хеширование, ограничивающее поведение будет постоянным для размера N, следовательно, O (1).

Answer 2

В общем , это O (1).

Answer 3

Для правильно реализованной хеш-таблицы при поиске амортизируется постоянная сложность времени.

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

Цитирование википедии:

Амортизированный анализ отличается от среднего показателя по случаю тем, что вероятность не учитывается; Амортизированный анализ гарантирует время выполнения одной операции в худшем случае.

Метод требует знания, какие серии операций возможны. Это чаще всего имеет место со структурами данных, состояние которых сохраняется между операциями. Основная идея заключается в том, что операция в наихудшем случае может изменить состояние таким образом, что наихудший случай не может повториться в течение длительного времени, что приведет к амортизации его стоимости.

Answer 4

Нет, Big O не определяет «наихудший случай», он определяет предел.Поиски на основе хеша (с хорошими алгоритмами хеширования, которые обеспечивают эффективное распределение значений и низкую частоту столкновений) прогрессируют к постоянному значению по мере увеличения количества элементов (они никогда не достигнут или этого постоянного значения, но в этом смысл ограничивать).

Answer 5

Я полагаю, что это в среднем означает O (1).

Answer 6

Нет, запись Big-O не обязательно ограничена худшим случаем.Как правило, вы увидите публикацию Big-O для лучших, средних и наихудших случаев.Просто большинство людей склонны фокусироваться на худшем случае.За исключением случая с хеш-таблицей, наихудший случай случается редко, поэтому использование среднего регистра имеет тенденцию быть более полезным.

Да, хорошая хеш-функция снижает вероятность коллизии.Неправильная хеш-функция может вызвать эффект кластеризации (когда хэш-значения разных значений одинаковы или близки к одному и тому же значению).Легко показать, что HashSet действительно может стать O (n), реализовав функцию GetHashCode таким образом, что она все время возвращает одно и то же значение.

В двух словах, да HashSet и Dictionary могут быть описаны как имеющие O (1) сложность во время выполнения, потому что акцент делается на сценарии среднего случая.

Кстати, Big-O также может использоваться для анализа амортизированной сложности,Амортизируемая сложность заключается в том, как последовательность отдельных (а иногда даже разных) операций ведет себя, когда они сгруппированы, как если бы они были одной большой операцией.Например, говорят, что в дереве преобразования амортизируется сложность O (log (n)) поиска, вставки и удаления, даже несмотря на то, что наихудшим случаем для каждого может быть O (n), а наилучшим - O (1).1011 *

Answer 7

Хеш-таблицы имеют не только среднюю производительность O (1), но если хеш-функция является случайной, для любого заданного процента P <100%, производительность, которая может быть получена P% времени из правильно спроектированной хэш-сказка O (1). Хотя экстремальные паразитарные случаи становятся все более и более тяжелыми с увеличением N, это уравновешивается тем фактом, что даже умеренно-паразитарные случаи становятся все менее и менее вероятными. </p>

Answer 8

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

Answer 9

Мое понимание Большого О - это то, что «наихудший случай» обычно относится к числу вовлеченных элементов. Таким образом, если функция должна была выполнить O (n) с 10 элементами, а O (n в квадрате) со 100 или более (не уверен, что такой алгоритм действительно существует), то алгоритм считается O (n в квадрате).