Почему успешный поиск в связанной хеш-таблице имеет в среднем временную сложность Θ(1+(n/m))?

Согласно «Алгоритмам: проектирование и анализ» Кормена и др. ожидаемое количество сравнений ключей при успешном поиске в хеш-таблице с отдельным разрешением коллизий цепочки составляет 1 + α/2 - α/2n [где α=n/m]. Интуитивное объяснение: так как это успешный поиск, то проверяем хотя бы один ключ (ищем его), и половину остальных ключей в цепочке.

Временная сложность: Θ(1 + 1 + α/2 - α/2n) = Θ(1 + α), по определению нотации большого тета.

За успешный поиск

ОБОЗНАЧЕНИЕ: α= n/m = коэффициент нагрузки

A) МАТЕМАТИЧЕСКОЕ ДОКАЗАТЕЛЬСТВО

1) Предположим, что новый элемент вставлен в конец связанного списка.

2) При вставке i-го элемента ожидаемая длина списка равна (i-1)/m .

3) В случае успешного поиска ожидаемое количество просмотренных элементов на 1 больше количества просмотренных элементов при вставке искомого элемента!

Таким образом, ожидаемое количество проверенных элементов равно

Расчет ожидаемого времени успешного поиска

Теперь добавьте «1», чтобы обозначить время для вычисления хеш-функции.

Мы получили,

Окончательный ответ

B)ИНТУИЦИЯ Для успешного поиска вы вычислите хэш-функцию O(1) и пройдете в среднем по половине ключей в цепочке.

Суммарное время на успешный и неуспешный поиск в абсолютном выражении не равно. Они равны только тогда, когда мы говорим об асимптотических обозначениях.

Общее время успешного поиска будет равно 1 + количество элементов в цепочке списка до требуемого ключа. Затем эта проблема сводится к поиску среднего количества элементов, которые будут добавлены после добавления определенного ключа в цепочный список.

Предположим, что необходимо найти ключ k1. Первоначально при составлении таблицы k1 добавляется в начало T[h(k1)]. Пусть количество элементов после добавления элемента с ключом k1 равно x. Таким образом, у нас все еще есть (n-x) элементов, которые нужно добавить в таблицу.

Поскольку это значение x может быть от 1 до n (поскольку ключ k1 всегда будет в таблице), поэтому мы суммируем (n-x) от 1 до n и умножаем на вероятность попадания в тот же индекс, где добавлен ключ k1. P(h(любой ключ) = 1/m

Таким образом, среднее значение получается: 1 + {(1/n) (Сумма (1/m)(n-x))}

Нижний предел и верхний предел x будут равны 1 и n соответственно. Получается, что Тета (1 + n/m).

Успешный поиск в цепочке имеет временную сложность O(1 + n/m), а не Θ(1+(n/m), потому что, если вы найдете свой элемент, вы можете остановиться. Нет необходимости смотреть на остальные элементы.