Согласно книге, которую я читаю, поиск интерполяции занимает O(loglogn) в среднем случае.
В книге предполагается, что каждое сравнение уменьшает длину списка от n до sqrt(n). Ну, нетрудно выработать O(loglogn) с учетом этого предположения.
Однако в книге больше не говорилось об этом предположении, за исключением того, что оно говорит, что это правильно.
Вопрос: может ли кто-нибудь объяснить, почему это так?
Это зависит от равномерного распределения входа (без такого предположения O (log n) - лучшее, что вы можете сделать теоретически, т.е. бинарный поиск является оптимальным). При равномерном распределении дисперсия вокруг sqrt (n), и в ожидаемом случае каждая итерация попадает в дисперсию цели. Таким образом, как вы говорите, пространство поиска идет от n → sqrt (n) на каждой итерации.
Представьте себе отсортированный массив, в котором каждая запись представляет собой число от одного до миллиона. Вы хотите посмотреть, есть ли 10000 в массиве. Поскольку 10000 составляет менее 99% от числа менее миллиона, если массив имеет хорошее распределение чисел, есть вероятность, что запись 10000, если она находится в массиве, находится очень близко к началу. Если мы рассмотрим запись на 1% процента пути через массив и обнаружим, что она больше 10000, мы исключили 99% массива за один шаг. Это намного лучше, чем двоичный поиск, который смотрит только на середину интервала и, следовательно, может удалять не более половины пространства поиска за раз. Это интуитивно, почему интерполяционный поиск в некоторых случаях может быть намного быстрее, чем двоичный поиск.
Чтобы увидеть строгий анализ того, почему ожидается, что это O (log log n), вам нужно будет прочитать учебник или документ по алгоритму.