Qidiruv usullarini tadqiq qilish va unga doir misollar
Ixtiѐriy ma’lumotlar majmuasi jadval ѐki fayl deb ataladi. Ixtiѐriy ma’lumot (ѐki tuzilma elementi) boshqa ma’lumotdan biror bir belgisi orqali farq qiladi. Mazkur belgi kalit deb ataladi. Kalit noѐb bo’lishi, ya’ni mazkur kalitga ega ma’lumot jadvalda yagona bo’lishi mumkin. Bunday noѐb kalitga boshlang’ich (birinchi) kalit deyiladi. Ikkinchi kalit bir jadvalda takrorlansada u orqali xam qidiruvni amalga oshirish mumkin. Ma’lumotlar kalitini bir joyga yig’ish (boshqa jadvalga) ѐki ѐzuv sifatida ifodalab bitta maydonga kalitlarni ѐzish mumkin. Agar kalitlar ma’lumotlar jadvalidan ajratib olinib alohida fayl sifatida saqlansa, u holda bunday kalitlar tashqi kalitlar deyiladi. Aks holda, ya’ni ѐzuvning bir maydoni sifatida jadvalda saqlansa ichki kalit deyiladi. Kalitni berilgan argument bilan mosligini aniqlovchi algoritmga berilgan argument bo’yicha qidiruv deb ataladi. Qidiruv algoritmi vazifasi kerakli ma’lumotni jadvalda topish ѐki yo’qligi aniqlashdan iboratdir . Agar kerakli ma’lumot yo’q bo’lsa, u holda ikkita ishni amalga oshirish mumkin: 1. ma’lumot yo’qligini indikasiya (belgilash) qilish 2. jadvalga ma’lumotni qo’yish. Faraz qilaylik, k – kalitlar massivi. Har bir k(i) uchun r(i) – ma’lumot mavjud. Key – qidiruv argumenti. Unga rec - informasion ѐzuv mos qo’yiladi. Jadvaldagi ma’lumotlarning tuzilmasiga qarab qidiruvni bir necha turlari mavjud. 1. Ketma-ket qidiruv Mazkur ko’rinishdagi qidiruv agar ma’lumotlar tartibsiz ѐki ular tuzilishi noaniq bo’lganda qo’llaniladi. Bunda ma’lumotlar butun jadval bo’yicha operativ xotirada kichik adresdan boshlab, to katta adresgacha ketma- ket qarab chiqiladi. Massivda ketma-ket qidiruv (search ozgaruvchi topilgan element raqamini saqlaydi).
2. Indeksli ketma-ket qidiruv Mazkur korinishdagi qidiruv amalga oshirilaѐtganda ikkita jadval tashkil qilinadi: o’z kalitiga ega ma’lumotlar jadvali (o’sish tartibida tartiblangan) va indekslar jadvali, bu xam ma’lumotlar kalitidan iborat- u, lekin bu kalitlar asosiy jadvaldan aniq bir interval orqali olingan. (2-chizma). Boshida berilgan argument boyicha ketma-ket qidiruv indekslar jadvalida amalga oshiriladi. Qachonki, biz berilgan kalitdan kichik kalitni aniqlaganimizda, asosiy jadvalda qidiruvni quyi chegarasini ornatamiz - low, keyin esa yuqori chegarani - hi, yani ( kind > key ). Masalan, key = 101. Qidiruv tola jadval boyicha emas, balki low dan hi gacha davom etadi.
3. Ketma-ket qidiruvni samaradorligi Ixtiѐriy 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 boladi: C = 1 n, C = (n + 1)/2. Umuman olganda royxatda xam samaradorlik yuqoridagi kabi boladi. Garchi massivda xam boglangan royxatda xam qidiruv samaradorligi bir xil bolsada, malumotlarni massiv va royxat korinishda tasvirlashning oziga xos kamchilik va afzalliklari mavjud. Qidiruvning maqsadi - quyidagi jaraѐnlarni bajarilishidan iborat: 1) Topilgan ѐzuvni o’qish. 2) Qidirilaѐtgan ѐzuv topilmasa, uni jadvalga qo’yish. 3) Topilgan ѐzuvni o’chirish. Birinchi jaraѐn (qidiruvning o’zi) massiv uchun ham ro’yxat uchun ham bir xil bo’ladi. Ikkinchi va uchinchi jaraѐnda 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 bolishi mumkin barcha xolatlar teng extimolli deb olinsa, u holda qidiruv samaradorligini quyidagicha xisoblash mumkin: Belgilashlar kiritib olamiz: m indeks olchovi; m = n / p; p qadam olchovi Q = (m+1)/2 + (p+1)/2 = (n/p+1)/2 + (p+1)/2 = n/2p+p/2+1 (*) Q ni p boyicha 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
Transpozisiya usuli Ushbu usulda topilgan element roxatda bitta oldingi element bilan orin almashtiriladi. Agarda mazkur elementga kop murojaat qilinsa, bittadan oldinga surilib borib natijada royxat boshida boladi.
Chizma. Qoshni elementlarni ornini almashtirish r ishchi korsatkich q ѐrdamchi ko’rsatkich, r dan bitta qadam orqada bo’ladi s - ѐrdamchi ko’rsatkich, q dan ikkita qadam orqada bo’ladi.