Почему длина списка уменьшается до sqrt (n) после каждого сравнения в интерполяционном поиске?

Question

Согласно книге, которую я читаю, поиск интерполяции занимает в среднем O(loglogn).
В книге предполагается, что каждое сравнение уменьшает длину списка с n до sqrt(n).Что ж, нетрудно определить O(loglogn) с учетом этого предположения.
Однако в книге больше не говорится об этом предположении, за исключением того, что говорится, что это правильно.

Вопрос: кто-нибудь может объяснить, почему это так?

Answer 1

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

Answer 2

Представьте себе отсортированный массив, в котором каждая запись представляет собой число от одного до миллиона.Вы хотите посмотреть, если 10000 в массиве.Так как 10000 - это менее 99% от чисел менее одного миллиона, если массив имеет хорошее распределение чисел, есть вероятность, что запись 10000, если она находится в массиве, очень близка к началу.Если мы посмотрим на запись 1% процентов пути через массив и обнаружим, что она больше 10000, мы удалили 99% массива за один шаг.Это намного лучше, чем бинарный поиск, который просматривает только середину интервала и, следовательно, может исключать только половину пространства поиска за раз.Это интуитивно понятно, почему интерполяционный поиск в некоторых случаях может быть намного быстрее, чем бинарный поиск.

Чтобы увидеть строгий анализ того, почему он должен быть O (log log n), вам придется прочитать учебник илистатья по алгоритму.