Algoritmlar va berilganlar strukturalari


Qidiruv algoritmlarning samaradorligi



Yüklə 0,65 Mb.
səhifə12/14
tarix14.12.2023
ölçüsü0,65 Mb.
#177515
1   ...   6   7   8   9   10   11   12   13   14
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
  1. Qidiruvni mukammallashtirish usullari





  1. Mukammal qidiruv daraxti



  1. 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.





Yüklə 0,65 Mb.

Dostları ilə paylaş:
1   ...   6   7   8   9   10   11   12   13   14




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©azkurs.org 2024
rəhbərliyinə müraciət

gir | qeydiyyatdan keç
    Ana səhifə


yükləyin