Сложность времени для хеш-таблиц при вставке и поиске

Question

, глядя на Википедию для хэш-таблиц, говорит, что вставка и поиск - O (1) .Но меня беспокоит то, что мой учитель сказал мне, что только поиск равен O (1) и что хеширование равно O (s) , где s длина строки.Разве вставка и поиск не должны быть O (s) вместо этого.Где написано хэширование ( s ) + поиск ( s ) = O (хеширование ( s ) + поиск ( s )) =О (* 1 029 * S ).

Может ли кто-нибудь объяснить мне, как правильно написать сложность времени в больших O-обозначениях для хеш-таблиц и почему?Если предположить, что это идеальное хеширование и никаких столкновений не происходит.

Answer 1

Хеш-таблицы используются не только для строк.Сложности O (1) для вставки и поиска в целом относятся к хеш-таблицам и учитывают только известные операции.

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

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

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

Answer 2

Этот вопрос очень похож на вопрос, который я задал: Является ли поиск в хэш-таблице O (1)?

Принято, что для хеш-таблиц "время"измеряется в сравнениях, а не операциях.Вот полный ответ, цитируемый:

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

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

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

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