|
Qidiruv algoritmlari
|
| bet | 3/3 | | Sana | 29.09.2022 | | Hajmi | 102.53 Kb. | | #26577 |
Bog'liq Qidiruv algoritmlariAlgoritm:
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 + у +1) + I = 0
dp dp 2 p2 2
Bu yerda
p2=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.
|
| |
