Время выполнения линейного зондирования на хеш-таблице

Question

Каково время работы (большой Oh) для линейного зондирования при вставке, удалении и поиске.

Спасибо

Answer 1

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

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

Если ваша хеширующая функция достаточно однородна, вы можете рассчитать вероятность столкновений, используя проблему дня рождения, и по этим вероятностям рассчитать ожидаемые длины зондирования.