Структуры и алгоритмы обработки данных

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


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 =

+1

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

)



Содержание раздела