Muhammad al-Xorazmiy nomidagi Toshkent axborot texnalogiyalari universiteti

Muhammad al-Xorazmiy nomidagi
Toshkent axborot texnalogiyalari universiteti
Qarshi filiali “Kompyuter injiniringi” Fakulteti
KI-11-21S guruh talabasi Qudratov Shavkat
Ma’lumotlar tuzilmasi va algoritmlar
2-MUSTAQIL ISH
Reja;
1 . Ma’lumotlarni qidirish usullari, algoritmlari va ularning
samaradorligi.
2 . Chiziqli qidiruv. Binar qidiruv. Qidirish usullari samaradorligi
va optimallashtirish.
3 . Saralash tushunchasi va uning vazifasi.
Kompyuter va kompleks tizimlarida ma’lumotlarni qayta
ishlashda qidiruv asosiy va keng foydalanadigan amallardan biri
hisoblanadi.
QIDIRUV bu ma’lumotlarning orasidan ma’lum bir belgilarga
mos ma’lumotlarni topish yoki yo’qligini aniqlash jarayonidir.
Qidiruvning maqsadi - quyidagi jarayonlarning birini
bajarilishidan iborat:
topilgan yozuvni oʼqish;
qidirilayotgan yozuv topilmasa, uni jadvalga qoʼshish;
topilgan yozuvni oʼchirish.
Qidiruvni amalga oshirayotganda 3ta xususiyat(atribut)ni
ajratish mumkin:
1) Ma’lumotlar majmuasi - bu fayl yoki jadval ko’rinishidagi
berilgan ma’lumotlar jamlanmasi (to’plami).
2) Kalit - ixtiyoriy maʼlumot (yoki tuzilma elementi) boshqa
maʼlumotdan farqlashning biror bir belgisi.
3) Qidiruv mezoni – bu qidirilayotgan kalit belgisi ma’lumotlar
yozuvlarida moslik sharti. (teng, yaqin, o’xshash va b.)
Kalit ikki xil boʼlishi mumkin:
* Birlamchi (takrorlanmaydi, noyob);
* Ikkilamchi (takrorlanadi).
Kalitlar saqlanishiga nisbatan ichki va tashqi deyiladi. Agar
kalitlar maʼlumotlar jadvalidan ajratib olinib alohida fayl sifatida
saqlansa, u holda bunday kalitlar tashqi kalitlar deyiladi. Аks
holda, yaʼni yozuvning bir maydoni sifatida jadvalda saqlansa
ichki kalit deyiladi.
CHIZIQLI QIDIRUV
Chiziqli qidiruv tarkibiy qidiruvga misol bo'ladi.
Aytaylik bizga massiv berilgan:
A={1,2,3,4,5,6,7,8,9,10} Bizga ushbu massivda biron bir element
bor yoki yo'qligini tekshira oladigan algoritm tuzish sharti
qo'yilgan.Ushbu masalani yechishda eng birinchi hayolga
keladigan usul - bu massivni ketma-ket har bir elementini
solishtirib chiqish va bu usul: Chiziqli qidiruv - Linear Search deb
ataladi.
Algoritm g'oyasi: Ma'lumotlar butun jadval bo'yicha operativ
xotirada kichik adresdan boshlab, to katta adressgacha ketma-
ket qarab chiqiladi.
BINAR QIDIRUV
Binar qidiruvning asosiy g'oyalaridan biri ketma-ket ikkiga
bo'lishga asoslanadi, ya'ni berilgan x ni massivning o'rtadagi
elementi bilan solishtiradi, agar katta bo'lsa oxiri va o'rtasi
orasidagi massivni oladi, agar kichkina bo'lsa boshi va o'rtasi
orasidagi massivni oladi, va har safar shu jarayon takrorlanib
boradi toki x element solishtirilayotgan massivning elementga
teng bo'lgunicha yoki massivning elementlari qolmaguncha.
CHIZIQLI VA BINAR QIDIRUV USULLARINING FARQLARI
Funksiyaga berilayotgan massiv Binar qidiruv uchun albatta
o'sish tartibida bo'lishi talab qilinadi, chiziqli qidiruv uchun esa
berilayotgan massiv qay tartibda bo'lishini ahamiyati yo'q.
Chiziqli qidiruvda elementlarni bittalab har birini tekshiriladi,
binarda esa algoritmidan kelib chiqib chiziqliga nisbatan ancha
kam solishtirish amali bajariladi.
Chiziqli qidiruvning ishlash vaqti ko'pi bilan O(n) va binar
qidiruvniki ko'pi bilan O(log n).
Elementni qidirishda solishtirish jarayoni ham ikki xil bo’ladi.
Chiziqli qidirish algoritmi faqat tenglikka asoslanadi. Ikkilik
qidirish esa tenglik, katta yoki kichiklikka qarab, o’z ishini
davom ettiradi.
Chiziqili qidirish algoritmi elementni array boshidan tartib bilan
qidiradi. Ikkilik qidirish algoritmida esa bu jarayon array
o’rtasidan boshlanib turlicha davom etishi mumkin.
Dasturlashda bu jarayon tasodifiy elementga murojaat (random
access) deb ataladi.
|