Jizzax filiali amaliy matematika fakulteti

OʻZBEKISTON RESPUBLIKASI OLIY VA O‘RTA MAXSUS TA’LIM VAZIRLIGI
MIRZO ULUG‘BEK NOMIDAGI MILLIY UNIVERSITETININIG
JIZZAX FILIALI



AMALIY MATEMATIKA FAKULTETI

«KOMPYUTER ILMLARI VA DASTURLASHTIRISH» kafedrasi

“ALGORITMLAR VA BERILGANLAR STRUKTURASI” FANIDAN

MUSTAQIL ISH

Mavzu: Qidirish algoritmlarini solishtirish

Bajardi: “KIDT” yoʻnalishi 2-kurs 11-21- guruh talabasi Doniyorova Munisa

Tekshirdi: Tojiyev Ma’ruf

Jizzax – 2023
Reja
1. Qidirish algoritmlari haqida
2. Qidirish algoritmlari maqsad va vazifalari mazmun mohiyati
3. Ba’zi tadbiqlar
Xulosa
Foydalanilgan adabiyotlar

Kirish
Qidirish algoritmlari ma'lum bir narsani topish uchun ishlatiladigan algoritmlardir. Bu narsa misol uchun, bir arrayda ko'p elementlar o'zaro bog'liq bo'lganda, yoki bir matn ichidagi ma'lum bir so'zni izlashda yoki fayl tizimida bir faylni topishda yoki boshqa bir ko'plab masalarda ishlatilishi mumkin.
Qidiruv masalasini shakllantirish quyidagicha bosqichda amalga oshiriladi:
1-bosqichda. Ma’lumotlarni yig’ish, to’ldirish.
2-bosqichda. Ma’lumotlarni tashkil etish (tartiblash va saralash);
3-bosqichda. Ma’lumotlarni olish (hususiy qidiruv);
Qidirish algoritmlari quyidagi turlarga bo'linadi:
Binary qidirish: Bu algoritm faqat tartiblangan elementlar uchun ishlatiladi. Misol uchun, tartiblangan arrayda bir elementni topish uchun bu algoritm ishlatiladi. Bunday algoritmlar bir nechta kichik to'xtatish birlashmalari bilan ham osonlashtiriladi. Bunday algoritmlar bo’l va hukumronlik qil qoidasiga asoslangan.

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.
Chiziqli qidirish algoritmi juda oddiy algoritm bo'lib, u arraydagi har bir elementni qidirilayotgan element bilan birma-bir solishtirib chiqadi. Algoritm murakkabligi O(n) bo'lib, bu real hayotda juda ham sekin bo'lishi mumkin.Tasavvur qilaylik Facebookning 1 mlrd foydalanuvchisi bor va foydalanuvchi o'z profiliga kirmoqchi. Bunda Facebook foydalanuvchi loginini chiziqli qidirishdan foydalanib tekshiradigan bo'lsa va bunda kompyuter sekundiga 10⁶ ta loginni tekshirgan taqdirda ham, o'sha foydalanuvchi profiliga kirishi uchun 1000 soniya (16.6 daqiqa) kutishi kerak bo'lardi. Shu sababli ham bunday holatlar uchun bizga samaraliroq algoritmlar kerak bo'ladi



Hash qidiruv: Bu algoritm bir elementni qidirishni osonlashtirish uchun foydalaniladi. Har bir element uchun unikal bir "key" yaratiladi, shuning uchun qidiruv tezlashtiriladi. Misol uchun, bitta matndagi bir so'zni qidirish uchun, bu so'zning "hash"ini yaratish va shu "hash"ni bazada qidirish uchun ishlatish mumkin.