• Algoritmning tahlili
    		•

    Qidiruv algoritmlari




    Download 102.53 Kb.
    bet3/3
    Sana24.02.2022
    Hajmi102.53 Kb.
    #18021
    1   2   3
    Bog'liq
    qidiruv algoritmlari
    123123123 rasskraska, 1-Ma`ruza, 631-19 guruh Toshboyev Jaloliddin KT 5-lab, 6-Maruza.Taqdimotlarni yaratish texnologiyalari, Labaratoriya ishi 3 Mobil ilovalarini ishlab chiqish Orifjanov Shavkatbek, Smart city, amaliyot 10, Laboratoriya ishi 11-12, ehtimollar test belgilangan, ЗАДАНИЕ 3 , 9-ma\'ruza 2021-2022 IRT, xisob ishchi dastur 2019-2020, (KOICA) Application Guideline 2022, KOMPYUTER NAZORATI PRINTSIPLARI
    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 + у +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.




    Download 102.53 Kb.
    1   2   3




    Download 102.53 Kb.