Ketma-ket qidiruvni samaradorligi
Ixtiyoriy qidiruvning samaradorligi jadvaldagi ma’lumotlarning kalitlari bilan solishtirish soni – C bilan baholanishi mumkin. Agar taqqoslashlar (solishtirishlar) 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 ham samaradorlik yuqoridagi kabi bo’ladi. Garchi massivda ham, bog’langan ro’yxatda ham qidiruv samaradorligi bir xil bo’lsada, ma’lumotlarni massiv va ro’yxat mo’rinishda tasvirlashning o’ziga xos kamchilik va afzalliklari mavjud. Qidiruvning maqsadi – quyidagi jarayonlarni bajarilishidan iborat:
Topilgan yozuvni o’qish.
Qidirilayotgan yozuv topilmasa, uni jadvalga qo’yish;
Topilgan yozuvni o’chirish.
Birinchi jarayon (qidiruvning o’zi)massiv uchun ham bir xil bo’ladi. Ikkinchi va uchinchi jarayonda esa qidiruv ro’yxatli tuzilmada samaraliroq bo’ladi (sababi massivda elementlarni siljitish lozim).
Agar k massivda elementlarni siljitishlar soni bo’lsa, u holda k = (n + 1)/2 bo’ladi.
Indeksli ketma-ket qidiruvning samaradorligi
Agar bo’lishi mumkin barcha holatlar teng ehtimolli deb olinsa, u holda qidiruv samaradorligini quyidagicha hisoblash mumkin:
Belgilashlarni 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 p2 + 1/2 = 0
Bu yerdan
p2=n ; n p
(*) ifodada р o’rniga ропт ni qo’yib quyidagi taqqoslashlar sonini olamiz:
Q = +1 n
Demak, indeksli ketma-ket qidiruvni samaradorligi tartibi O ( ) bo’ladi. n
Dostları ilə paylaş: |
