Эффективность индексно-последовательного поиска

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

Введем обозначения: m - размер индекса; m = n / p;

p - размер шага

Q = (m+1)/2 + (p+1)/2 = (n/p+1)/2 + (p+1)/2 = n/2p+p/2+1

Продифференцируем Q по p и приравняем производную нулю:

dQ/dp=(d/dp) (n/2p+p/2+1)= - n / 2 p2 + 1/2 = 0

Отсюда

p2=n ;

Подставив ропт в выражение для Q, получим следующее количество сравнений:

Q =

Порядок эффективности индексно-последовательного поиска O (

)