Mavzu: Chiziqli va ikkilik qidiruv usullarini taqdiq qilish

Erkinov Ollashukur

943-19 guruh talabasi

Ma'lumotlar ba'zasi va algoritmi fanidan

Mustaqil ishi.

Mavzu: Chiziqli va ikkilik qidiruv usullarini taqdiq qilish.

mumiy jihatlar

Ikki algoritm uchun umumiy bo’lgan jihatlar, albatta, bu ularning qiladigan ishi va beradigan natijasida. Ya’ni ikki algoritm ham arraydan qandaydir elementni birorta shart asosida tekshiradi va element indeksini javob sifatida qaytaradi.

Bundan tashqari ikkala algoritmda ham ishlashi uchun qo’shimcha xotiradan joy talab qilinmaydi, ya’ni ikki algoritmning hotira bo’yicha murakkabliki O(1) ga teng.

Biz uchun esa hozir ularning farqli tomonlari muhimroq

Algoritmlarning farqli tomonlari

Kiruvchi ma’lumot

Bu ikki algoritmning asosiy farqi, oldingi darslarimizda ham ko’p marta ta’kidlaganimizdek, 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.

2. Qidirish jarayoni

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. Bu narsa qidirish algoritmi ish bajarayotgan ma’lumot tuzilmasi uchun muhim. Chunki ba’zi tuzilmalarda tasodifiy elementga birdan murojaat qilishning iloji yo’q. Masalan, stack, queue, linked list va h.k.

3. Solishtirish

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.

4. Vaqt bo’yicha murakkablik

Ikkita bir xil vazifani bajaruvchi algoritmlarni solishtirayotgan paytda ularning ishlash tezligini solishtirib ko’rmasdan iloj yo’q albatta. Demak,

Chiziqli qidirish ishlash tezligi:

Eng yaxshi holatda: O(1)

O’rtacha holatda: n(n+1)/2n = O(n)

Eng yomon holatda: O(n)

Ikkilik qidirish ishlash tezligi:

Eng yaxshi holatda: O(1)

O’rtacha holatda: logn(logn+1)/2logn = O(logn)

Eng yomon holatda: O(logn)

Shunday qilib yuqorida sanab o’tganlarimiz chiziqli qidirish va ikkilik qidirish algoritmlari farqlari va umumiy jihatlari edi.