13-Mavzu: Ma’lumotlarni qidiruv algoritmlari Reja

Algoritm:

Psevdokodda yozilishi:

i = 1

while (i <= m) and (kind(i) <= key) do i=i+1

endwhile

if i = 1 then low = 1 else low = pind(i-1)

endif

if i = m+1 then hi = n else hi = pind(i)-1

endif

for j=low to hi if key = k(j) then

search=j

Paskal tilida yozilishi:

i:=1;

while (i <= m) and (kind[i] <= key) do i=i+1;

if i = 1 then low:=1 else low:=pind[i-1]; if i = m+1 then hi:=n else hi:=pind[i]-1; for j:=low to hi do

if key = k[j] then begin

search:=j;

exit;

end;

search:=0;

exit;

return

endif

next j

search=0

return

Algoritmning tahlili. Agar barcha holatlar uchun teng ehtimollik deb hisoblansa, u holda qidirish samaradorligini quyidagicha aniqlash mumkin:

Belgilashlar kiritamiz: m - indeks o‘lchami; m = n / p;

+1

m+1 p +1

Q = +

2
p - qadamlar o‘lchami

2


Yuqoridagi

tenglashtiramiz:

formulada Q ni p bo‘yicha differetsiallaymiz va nolga

d^ ^d Qp + у +¹) ₊ I _{= 0}

dp dp 2 p² 2

Bu yerda

p²=n; p =4n

Q ning ifodasida popt ning qiymatini o‘rniga qo‘yib, quyidagicha taqqoslashlar soniga ega bo‘lamiz:

Q = 4n +1

Q(Vn) indeksli ketma-ket qidirishning samaradorlik darajasi hisoblanadi.

Nazariy savollar

1. 
   Qidiruv tushunchasini tushuntirib bering?
   
2. 
   Ketma-ket qidiruv algoritmini tushuntirib bering?
   
3. 
   Algoritm tahlilini misollar yordamida tushuntirib bering.