Лекция Массачусетского технологического института НЕПРАВИЛЬНО? Анализ открытой адресации при хешировании

В следующей лекции Массачусетского технологического института: https://www.youtube.com/watch?v=JZHBa-rLrBA в 1:07:00 ,профессор научил считать количество проб при безуспешном поиске.

Но мой метод расчета не совпадает с его. Мой ответ:

Количество запросов = введите здесь описание изображения

м = нет. слотов в хеш-таблице

п = нет. элементов (ключей)

Объяснение:

1. Хэш-функция может попасть в пустой слот с вероятностью m-n/m.

2. Или он может попасть в занятый ключевой слот с вероятностью n/m.

3. Теперь в случае 2 нам придется снова вызывать хеш-функцию, и есть два шанса: (i) мы получим слот без ключа с вероятностью (m-n)/(m-1). (ii) Мы получаем слот с ключом с вероятностью (n-1)/(m-1).

4. Теперь повторите случай 3, но с другими вероятностями, как показано на рисунке.

Почему я получаю другой ответ. Что с этим не так?


algorithm hash probability hashtable clrs
person Naman Agarwal    schedule 01.08.2015    source источник
comment
Не совсем связан с программированием. Может лучше подойти для Math.SE.   -  person Gumbo    schedule 01.08.2015

Ответы (1)


arrow_upward
5
arrow_downward

Задача просит нас найти ожидаемое количество тестов, которые необходимо выполнить в хеш-таблице.

Вы должны сделать один, несмотря ни на что, поэтому у вас есть 1 для начала. Тогда есть шанс n / m, что у вас есть столкновение. Вы правильно поняли это в своем объяснении.

Если у вас есть коллизия, вы должны сделать еще один зонд (а может быть, и больше). И так далее, поэтому профессор получает ответ:

1 + (n / m)(1 + ((n - 1) / (m - 1))(1 + ...))

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

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

Это очень хорошо объясняется в лекции, на которую вы ссылаетесь, если вы внимательно посмотрите до конца.

person IVlad    schedule 01.08.2015