Қидирув алгоритмларини тадқиқ қилиш



Download 12,36 Kb.
bet1/2
Sana16.03.2022
Hajmi12,36 Kb.
#497890
  1   2
Bog'liq
Қидирув

Қидирув алгоритмларини тадқиқ қилиш

  • 10-Мавзу: Қидирувнинг оддий алгоритмлари

Қидирув тушунчаси ва унинг вазифаси

  • Маълумотларни қайта ишлашда қидирув асосий амаллардан бири бўлиб, унинг вазифаси берилган аргумент (калит) бўйича маълумотлар базаси ичидан мазкур аргументга мос маълумотларни топиш ёки йўқлигини аниқлашдан иборат.
  • Агар керакли маълумот йўқ бўлса, у ҳолда иккита ишни амалга ошириш мумкин:
    • маълумот йўқлигини белгилаш;
    • жадвалга маълумотни қўйиш.
  • Ихтиёрий маълумотлар мажмуаси жадвал ёки файл деб аталади. Ихтиёрий маълумот (ёки тузилма элементи) бошқа маълумотдан бирор бир белгиси орқали фарқ қилади. Мазкур белги калит деб аталади.
  • Калит икки ҳил бўлиши мумкин:
    • бирламчи(такрорланмайди, ноёб);
    • иккиламчи(такрорланади).

Қидирув тушунчаси ва унинг вазифаси

  • Таъриф. Агар калитлар маълумотлар жадвалидан ажратиб олиниб алоҳида файл сифатида сақланса, у ҳолда бундай калитлар ташқи калитлар дейилади. Акс ҳолда, яъни ёзувнинг бир майдони сифатида жадвалда сақланса ички калит дейилади.
  • Қидирувнинг мақсади - қуйидаги жараёнларнинг бирини бажарилишидан иборат:
    • топилган ёзувни ўқиш;
    • қидирилаётган ёзув топилмаса, уни жадвалга қўйиш;
    • топилган ёзувни ўчириш.
  • Фараз қилайлик, k – калитлар массиви бўлсин. Ҳар бир k(i) учун r(i) – маълумот мавжуд. Key – қидирув аргументи.
  • Жадвалдаги маълумотларнинг тузилмасига қараб қидирувни бир неча турлари мавжуд.

Қидирувнинг оддий алгоритмлари

  • Чизиқли ёки кетма-кет қидирув (массивда)
  • Алгоритм ғояси
  • Эслатма
  • Чизиқли алгоритмдан агар маълумотлар жадвали тартибсиз ёки улар тузилиши ноаниқ бўлса фойдаланиш тавсия этилади.
  • Изоҳ
  • Агар маълумотлар жадвали массив кўринишда бўлса, у ҳолда, асосан, алгоритм натижаси сифатида топилган элемент ўрни қайтарилади.
  • Чизиқли қидирувни амалга ошириш процедураси
  • Massivda ketma-ket qidiruv algoritmi samaradorligini bajarilgan taqqoslashlar soni M bilan aniqlash mumkin. Mmin = 1, Mmax = n. Agar ma’lumotlar massiv yacheykasida bir hil extimollik bilan taqsimlangan bo‘lsa, u holda Msr (n + 1)/2 bo‘ladi.
  • Agar kerakli element jadvalda bo‘lmasa va mazkur elementni jadvalga qo‘shish lozim bo‘lsa, u holda yuqoridagi dasturdagi oxirgi ikkita operator quyidagiga almashtiriladi.
  • Чизиқли қидирув (боғланган рўйхатда)
  • Agar ma’lumotlar jadvali bir bog‘lamli ro‘yxat ko‘rinishida berilgan bo‘lsa, u holda ketma-ket qidiruv ro‘yxatda amalga oshiriladi. Ro‘yxatli tuzilmaning afzalligi shundan iboratki, ro‘yxatga elementni qo‘shish yoki o‘chirish tez amalga oshadi, bunda qo‘shish yoki o‘chirish element soniga bog‘liq bo‘lmaydi, massivda esa elementni qo‘shish yoki o‘chirish taxminan barcha elementlarni yarimini siljitishni talab qiladi. Umuman olganda ketma-ket qidiruv samaradorligini oshirish mumkin. Faraz qilaylik, kun davomida ma’lumotlar yig‘ilib, kechqurun ular qayta ishlansin. Ma’lumotlar to‘plangandan keyin ular saralanadi.
  • Индексли кетма-кет қидирув
  • Эслатма
  • Индексли кетма-кет алгоритмдан агар маълумотлар жадвали тартибланган бўлса фойдаланиш мумкин бўлади.
  • Индексли кетма-кет қидирув
  • Mazkur ko‘rinishdagi qidiruv amalga oshirilayotganda ikkita jadval tashkil qilinadi: o‘z kalitiga ega ma’lumotlar jadvali (o‘sish tartibida tartiblangan) va indekslar jadvali, bu xam ma’lumotlar kalitidan iboratu, lekin bu kalitlar asosiy jadvaldan aniq bir interval orqali olingan. 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.
  • Ketma-ket qidiruvni samaradorligi Ixtiyoriy qidiruvning samaradorligi jadvaldagi ma’lumotlarning kalitlari bilan solishtirish soni – S bilan baxolanishi mumkin. Massivda ketma-ket qidiruvning samaradorligi quyidagicha bo‘ladi: C = 1 n, C = (n + 1)/2. 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.

Download 12,36 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