Algoritmlar va berilganlar strukturalari

Qidiruv algoritmlarning samaradorligi

. Ketma-ket qidiruvni samaradorligi Ixtiyoriy qidiruvning samaradorligi jadvaldagi ma’lumotlarning kalitlari bilan solishtirish soni – S bilan baxolanishi mumkin. Agar taqqoslashlar (solishtirish) soni qancha kichik bo’lsa, qidiruv algoritmi samaradorligi shuncha yaxshi bo’ladi. Massivda ketma-ket qidiruvning samaradorligi quyidagicha bo’ladi: C = 1 n, C = (n + 1)/2. Umuman olganda ro’yxatda xam samaradorlik yuqoridagi kabi bo’ladi. Garchi massivda xam bog’langan ro’yxatda xam qidiruv samaradorligi bir xil bo’lsada, ma’lumotlarni massiv va ro’yxat ko’rinishda tasvirlashning o’ziga xos kamchilik va afzalliklari mavjud. Qidiruvning maqsadi - quyidagi jarayonlarni bajarilishidan iborat:

1. 
   Topilgan yozuvni o’qish. 2) Qidirilayotgan yozuv topilmasa, uni jadvalga qo’yish. 3) Topilgan yozuvni o’chirish. Birinchi jarayon (qidiruvning o’zi) massiv uchun ham ro’yxat uchun ham bir xil bo’ladi. Ikkinchi va uchinchi jarayonda esa qidiruv ro’yxatli tuzilmada samaraliqroq bo’ladi (sababi massivda elementlarn siljitish lozim). Agar k massivda elementlarni siljitishlar soni bo’lsa, u xolda k = (n + 1)/2 bo’ladi. 4. Indeksli ketma-ket qidiruvni samaradorligi Agar bo’lishi mumkin barcha xolatlar teng extimolli deb olinsa, u holda qidiruv samaradorligini quyidagicha xisoblash mumkin: Belgilashlar kiritib olamiz: m – indeks o’lchovi; m = n / p; p – qadam o’lchovi Q = (m+1)/2 + (p+1)/2
   

= (n/p+1)/2 + (p+1)/2 = n/2p+p/2+1 (*) Q ni p bo’yicha differensiallab uni nolga tenglashtiramiz: dQ/dp=(d/dp) (n/2p+p/2+1)= - n / 2 p 2 + 1/2 = 0 Bu yerdan p 2 =n ; n p opt

44. Qidiruvni mukammallashtirish usullari

44. 
    Mukammal qidiruv daraxti
    

44. Binar qidiruv (teng ikkiga bo’lish usuli)

Binar daraxt bo’yicha qidiruv funksiyasi

Mazkur funksiyaning vazifasi shundan iboratki, u berilgan kalit bo’yicha daraxt tuguni qidiruvini amalga oshiradi. Qidiruv operatsiyasining davomiyligi daraxt tuzilishiga bog’liq bo’ladi. Haqiqatdan, agar elementlar daraxtga kalit qiymatlari o’sish (kamayish) tartibida kelib tushgan bo’lsa, u holda daraxt 5.7-rasmdagidek bir tomonga yo’nalgan ro’yhat hosil qiladi (chiqish darajasi bir bo’ladi, ya’ni yagona shoxga ega), masalan:

4.7-rasm. Bir tomonlama yo’naltirilgan binar daraxt tuzilishi

Bu holda daraxtda qidiruv vaqti, bir tomonlama yo’naltirilgan ro’yhatdagi kabi bo’lib, o’rtacha qarab chiqishlar soni N/2 bo’ladi. Agar daraxt muvozanatlangan bo’lsa, u holda qidiruv eng samarali natija beradi. Bu holda qidiruv dan ko’p bo’lmagan elementlarni ko’rib chiqadi.

Qidiruv funksiyasini ko’rib chiqamiz. search fuksiyasi daraxtdan key kalitga mos elementning adresini aniqlaydi.