Chiziqli qidirish usulini tadqiq qilish

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.

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.

XULOSA

Ko'rib turganimizdek, ikkilik qidirish chiziqli qidirishdan ko'ra samaralidir, chunki har safar biz qolgan massivning yarmini qidirishimiz kerak.

Ikkilik qidirish algoritmi ishlashi uchun array saralangan bo’lishi shart. Chiziqli qidirish algoritmida esa bu narsaga hojat yo’q. Aynan shu jihati bilan chiziqli qidirish algoritmi ikkilik qidirishdan ko’ra ustunlik qilishi mumkin. Chunki ba’zi holatlarda ma’lumot saralanmagan bo’lishi va uni saralash ko’proq vaqt olib qo’yishi mumkin.

Vikipediyaga ko'ra, o'rash uchun: kompyuter fanida algoritmlarni kirish vaqti kattalashgan sari ularning ishlash vaqti yoki makon talablariga qarab tasniflash uchun katta O yozuvi ishlatiladi. Bu funktsiyalarni o'sish sur'atlariga ko'ra tavsiflaydi. Shunday qilib, chiziqli qidirish uchun, massivning kattalashishi bilan ishning eng murakkab holati O (n) bo'ladi.

Foydalanilgan adabiyotlar:

• Cms.tuit.uz maruza matnlari;
• sqlservertutorial.net
• jquery-az.com
• w3schools.com
• metanit.com
• Wikipediya.com
• Texnoman.uz