Сложность времени для заполнения хеш-таблицы?
Это домашнее задание, но я думаю, что-то упущено. Он спрашивает:
Укажите последовательность m клавиш для заполнения хэш-таблицы, реализованной с помощью линейного зондирования, чтобы время ее заполнения было минимальным.
А потом
Укажите другую последовательность m клавиш, но такую, чтобы время ее заполнения было максимальным. Повторите эти два вопроса, если в хэш-таблице реализовано квадратичное зондирование.
Я могу только предположить, что хеш-таблица имеет размер m, потому что это единственное данное число и потому, что мы использовали это письмо для адресации размера хеш-таблицы ранее при описании коэффициента загрузки. Но я не могу придумать какую-либо последовательность, которая сделала бы первое, не зная хеш-функцию, которая хэширует последовательность в таблицу.
Если это плохая хеш-функция, такая, что, например, она хэширует каждую запись в одном и том же индексе, то и минимальное, и максимальное время для ее заполнения займет O(n) времени, независимо от того, как выглядит последовательность. И в среднем, когда я предполагаю, что хеш-функция в порядке, как я должен знать, сколько времени потребуется этой хеш-функции для заполнения таблицы?
Разве эти вопросы не связаны с хэш-функцией сильнее, чем с хэшированной последовательностью?
Что касается второго вопроса, я могу предположить, что, независимо от хеш-функции, последовательность размером m с тем же ключом, повторенным m- times, обеспечит максимальное время, потому что это вызовет линейное зондирование со второй записи. Я думаю, что это займет O (N) время. Это верно?
2 ответа
Ну, идея этих вопросов - проверить ваше понимание стилей исследования. Для линейного зондирования, если происходит столкновение, вы просто проверяете следующую ячейку. И так будет продолжаться до тех пор, пока вы не найдете доступную ячейку для хранения ваших данных. Ваша хеш-таблица не должна быть размером m, но должна быть at least size m,
Первый вопрос: если у вас есть идеальная хеш-функция, какова сложность заполнения таблицы. Идеальная функция хеширования обращается к каждому элементу без коллизий. Таким образом, для каждого элемента в m вам нужно O(1) раз. Общая сложность составляет O (м).
Второй вопрос касается случая, когда hash(X)=cell(0), в котором все элементы будут искать до первой пустой ячейки (сразу за текущей заполненной таблицей).
Для первого элемента вы проверяете один раз -> O(1)
Для второго элемента вы проверяете дважды -> O(2)
для n-го элемента вы проверяете n раз -> O(n)
Всего у вас есть m элементов, так что -> O(n*(n+1)/2)
Для квадратичного зондирования у вас та же стратегия. Минимальный регистр такой же, но максимальный регистр будет иметь значение O(nlogn). (Я не решил, просто это мое обоснованное предположение.)
Эти вопросы не звучат ужасно, связанные с хэш-функцией, но было бы неплохо иметь. Вы, кажется, в значительной степени получаете это, все же. Для меня это звучит так, как будто вопрос больше касается "знаете ли вы, какой будет список наихудших вариантов ключей?" чем "вы знаете, как использовать плохие хэш-функции?"
Очевидно, что если вы придумаете последовательность, в которой все записи хэшируются в разные места, то у вас будет O(1) вставок за O(m) времени.
Для того, что вы говорите о хешировании всех ключей в одном и том же месте, каждая вставка должна принимать O(n), если это то, что вы предлагаете. Однако это не общее время для вставки всех элементов. Кроме того, вы можете рассмотреть возможность не буквального использования одного и того же ключа снова и снова, а использования ключей, которые будут приводить к одному и тому же месту в таблице. Я думаю, что условно, вставка одного и того же ключа должна привести к замене, хотя я не уверен на 100%.
Я заранее извинюсь, если предоставил слишком много информации или оставил что-то неясным. Этот вопрос кажется довольно сложным, за исключением части о том, что на самом деле он не знает хеш-функцию, и было довольно сложно действительно сказать много, не отвечая на весь вопрос.