Toshkent axborot texnologiyalari universiteti kompyuter injenirengi fakulteti

|
Toshkent axborot texnologiyalari universiteti kompyuter injenirengi fakulteti
|
Sana | 15.05.2024 | Hajmi | 285,15 Kb. | | #235581 |
Bog'liq malumotlar tuzilmasi KOMPYUTER INJENIRENGI FAKULTETI
“Ma’lumotlar tuzilmasi va algoritmlar” fanidan
Mavzu: Chiziqli va binar qidirish usullarini tadqiq qilish
Tolibjonov Samandar
53-variant
Dasturlashda eng ko’p qo’llaniladigan amallardan biri bu – ma’lumotlarni qidiruv. Qidiruvning birnechta asosiy variantlari mavjud bo’lib, ular uchun har xil algoritmlar yaratilgan.
Chiziqli qidiruv – ixtiyoriy funksiyaning qandaydir kesmadagi berilgan qiymatini qidirishga aytiladi. Bu algoritm oddiy algoritm hisoblanib, boshqa algoritmlardan, masalan binar qidiruvdan farqli tamoni funksiyaga hecha qanday cheklanish qo’yilmaydi va amalga oshirish oddiy hisoblanadi.
Chiziqli qidiruv algoritmi. Funksiya qiymatini izlash navbatdagi qiymatni (odatda chapdan o’nga argument oshishi tartibida amalga oshiriladi)oddiy taqqoslash orqali tekshiriladi. Masala ikki xil qo’yilishi mumkin:
1) Birinchi topilgan argumentni topish
2) Barcha argumentlarni topish.
Agar funkisya sifatida massiv argument sifatida massiv indeksi qo’llanilsa u holda chiziqli qidiruv natijasida berilgan massivdan bo’lgan shunday i indekslarni topish lozim.
Massiv: 45, 12 , 89, 12, -78, 12;
12 sonining pozitsiyalari 2, 4, 6;
Chiziqli qidiruv.
Oddiy chiziqli qidiruvda massivning har bir elementi bilan birma-bir tekshirib chiqiladi.
Bunda L va R o’zgruvchilar element qidiriladigan oraliq.
Har bir so’rovga O(n) amallar bajariladi. n – massiv elemenlari soni. Chiziqli qidiruv algoritmi qidirilayotgan interval kichik bo’lgan vaqtdagina effektiv bo’ladi.
Binar qidiruv
Aytaylik bizga tartiblangan n ta elementdan iborat arr[] massiv berilgan bo'lsin, va berilgan x ni arr[] ichidan qidirish funksiyasini tuzish sharti qo'yilsin.
Bu holatda eng oson yo'l sifatida chiziqli qidiruvni misol keltirish mumkin. Ammo bu usulning vaqt davomiyligi O(n) ni tashkil qiladi. Xuddi shu vazifa uchun biz binar qidir algoritmini ishlatsak bo'ladi.
Binar qidiruv
Qiyinlik darajasi: 5/10.
Eng zo'r ko'rsatkichi(vaqt): O(1)
Eng yomon ko'rsatkichi(vaqt): O(log n)
O'rtacha ko'rsatkichi(vaqt): O( log n)
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.
Masalan:
Biz bitta taqqoslashdan so'ng massivning yarim elementlarini hisobga olmasak ham bo'ladi.
1. x ni o'rtadagi element bilan solishtiramiz.
2. Agar rost bo'lsa, o'rtadagi elementni qaytaramiz.
3. Agar x katta bo'lsa, x ni massivni o'ng yarmini ichidan qidiramiz, yuqoridagi ketma-ketlikni bajargan holda.
4. Aks holda chap yarmi bilan binar qidiruvni amalga oshiramiz.
Quyida Binar qidiruvning rekursiya orqali amalga oshiramiz.
Dastur ishlaganda " X soni massivning 3 - elementi." degan yozuvni qaytaradi. Sababi massiv elementlari 0 dan boshlanadi.
Xulosa shuki Binar qidiruv Chiziqli qidiruvdan ancha tezroq ishlaydi.
Foydalanilgan adabiyotlar
Web saytlar:
https://uzbekdevs.uz
https://www.texnoman.uz
https://dokumen.tips
|
| |