Время выполнения для вставки n элементов в пустую хеш-таблицу

Question

Люди говорят, что он амортизирует O (1), чтобы положить в хеш-таблицу. Следовательно, положить n элементов должно быть O (n). Однако это не верно для больших n, поскольку, как сказал ответчик: «Все, что вам нужно для удовлетворения ожидаемого амортизированного O (1), - это расширение таблицы и перепрофилирование всего с помощью новой случайной хэш-функции в любое время столкновения».

Итак: каково среднее время выполнения вставки n элементов в хеш-таблицу? Я понимаю, что это, вероятно, зависит от реализации, поэтому укажите, о какой типе реализации вы говорите.

Например, если есть (журнал N) равномерно распределенных столкновений, и каждое столкновение происходит O (к), чтобы решить, где к текущий размер хеш-таблицы, то вы бы это рекуррентное соотношение:

T(n) = T(n/2) + n/2 + n/2 

(то есть вы тратите время на вставку n/2 элементов, тогда у вас есть столкновение, принимающее n/2 для разрешения, тогда вы делаете оставшиеся n/2 вставки без столкновения). Это все еще заканчивается O (n), поэтому yay. Но разве это разумно?

Answer 1

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

Answer 2

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

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

Answer 3

Люди говорят, что амортизация O (1) помещается в хэш-таблицу.

С теоретической точки зрения, это ожидается амортизируется O (1).

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

Вы можете ожидать достижения амортизируется O (1) с помощью dynamic perfect hashing:

Наивная я первоначально размещен был перефразировать с новой случайной хэш-функции на каждом столкновении. (См. Также perfect hash functions) Проблема заключается в том, что для этого требуется O (n^2) пространство, от парадокса рождения.

Решение состоит из двух столовых столов, со второй таблицей для столкновений; разрешить конфликты на этом втором столе, восстановив его. В этой таблице будут элементы O (\ sqrt {n}), поэтому они будут расти до размера O (n).

На практике вы часто используете фиксированную хеш-функцию, потому что вы можете предположить (или не волнует, если) ваш вход является патологическим, так же, как вы часто быстро сортируете без предварительного доступа к входу.

Answer 4

Все O (1) говорят, что операция выполняется в постоянное время, и это не в зависимости от количества элементов в вашей структуре данных.

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

На практике это означает, что простые структуры данных, такие как деревья, являются обычно более эффективны, когда вам не нужно хранить много данных. По моему опыту я нахожу деревья быстрее до ~ 1k элементов (32-битные целые числа), а затем хеш-таблицы берут верх. Но, как обычно, YMMW.