Qidiruv algoritmlari. Axborot izlashning asosiy tamoyillari. Ketma-ket izlash. Izlashning tezlashtirilgan usullari

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
Qidiruv butun jadval bo‘yicha emas, balki low dan hi gacha amalga oshiriladi.


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;

cgjcgjcghdg

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.