Блог пользователя NikitaMikhaylov

Автор NikitaMikhaylov, история, 8 лет назад, По-русски

Всем привет!

Как вы, наверно, знаете доступ/добавление/удаление в хэш-таблице работает за O(1). Сегодня мы попытаемся улучшить эту оценку. Теперь рассмотрим реализацию хэш-таблицы с закрытой адресацией: пусть функция h равновероятно переводит каждый элемент множества A в множество B, те h: A → B, где A — множество возможных значений, а B — первые k натуральных чисел, для просты возьмем k = |A|. Если жи есть два элемента x, y для которых h(x) = h(y), то будем добавлять их в цепочку ячейки h(x) для разрешения коллизий. Вообще раз O оценка — это оценка сверху, то давайте далее полагать, что в каждую такую ячейку попадет t = 1 элементов. Тогда изменим способ хранения элементов со списка на set, но мы знаем, что время работы операций в set есть , но так как размер нашей ячейки t, то операции работают за , отсюда получаем, что n операции на нашей хэш-таблице отработают за O(n·0) = O(0).

  • Проголосовать: нравится
  • +32
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +47 Проголосовать: не нравится

спасибо тебе за хорошее настроение.

»
8 лет назад, # |
  Проголосовать: нравится +69 Проголосовать: не нравится

Кстати, если использовать хеш-таблицы, описанные в посте, вместо массивов, то время работы почти любого алгоритма можно будет скостить до О(0), ведь О(f(n)) * O(время доступа к хеш-таблице) = О(f(n)) * O(0) = О(0)

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +25 Проголосовать: не нравится

Статья божественная... Но после нее у меня возникает вопрос: чему равен в реальности log(O(...))?