Qidiruv usullarini tadqiq qilish va unga doir misollar



Download 45,61 Kb.
bet1/2
Sana28.01.2023
Hajmi45,61 Kb.
#904387
  1   2
Bog'liq
Qidiruv usullar


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 o’zgaruvchi topilgan element raqamini saqlaydi).




2. Indeksli ketma-ket qidiruv
Mazkur ko’rinishdagi 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 bo’yicha ketma-ket qidiruv indekslar jadvalida amalga oshiriladi. Qachonki, biz berilgan kalitdan kichik kalitni aniqlaganimizda, asosiy jadvalda qidiruvni quyi chegarasini o’rnatamiz - low, keyin esa yuqori chegarani - hi, ya’ni ( kind > key ). Masalan, key = 101. Qidiruv to’la jadval bo’yicha 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 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 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 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

Transpozisiya usuli
Ushbu usulda topilgan element ro’xatda bitta oldingi element bilan o’rin almashtiriladi. Agarda mazkur elementga ko’p murojaat qilinsa, bittadan oldinga surilib borib natijada ro’yxat boshida bo’ladi.


Chizma. Qo’shni elementlarni o’rnini almashtirish r – ishchi ko’rsatkich q – ѐrdamchi ko’rsatkich, r dan bitta qadam orqada bo’ladi s - ѐrdamchi ko’rsatkich, q dan ikkita qadam orqada bo’ladi.

Download 45,61 Kb.

Do'stlaringiz bilan baham:
  1   2




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish