Какова среда выполнения квадратичного зондирования в HashTable?

Question

Этот вопрос аналогичен Linear Probing Runtime, но касается квадратичного зондирования.

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

Каким будет время выполнения для квадратичного зондирования? Я знаю, что квадратичные зонды квадратичным образом -1, 4, 9, 16, ..... Моя первоначальная мысль заключалась в том, что это некоторая вариация log n(экспоненциальная), но нет единой базы.

Answer 1

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

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