Предположим, мы применили close hashing алгоритм на (4, 2, 12, 3, 9, 11, 7, 8, 13 и 18). И предположим, что длина хэш-таблицы равна изначально. Как найти такую таблицу хэшей можно в O (1) время в худшем случае.временная сложность алгоритма замкнутого хеширования
Это действительно не имеет значения, что вы делаете. Поскольку набор данных предопределен, существует постоянная верхняя граница поиска наихудшего случая для любой хеш-функции (при условии, что хеш-функция будет завершена). (Если один элемент занимает больше времени, чем другие, то есть верхняя граница.) Из константной верхней границы вытекает сложность О (1). QED.
, так что вы всегда подразумеваете временную сложность близкого хэширования O (1)? или я неправильно понял? – user2076685
@ user2076685 № Сложность времени - это функция некоторой переменной (ов). В вашем вопросе не содержится ничего, что может измениться. Нет N, поэтому любая возможная функция N, такая как N^2 или log (N) или просто N, исключается. Оставшаяся возможность, помимо программы, не заканчивающейся, равна O (1). – Potatoswatter
На самом деле я в замешательстве. это вопрос экзамена! Не могли бы вы рассказать мне, как я могу ответить на этот вопрос. Я новичок в этой теме. не могли бы вы объяснить это проще? – user2076685