Farg‘ona davlat universiteti

Algoritmlarning farqli tomonlari

1. 
   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:

1. 
   Eng yaxshi holatda: O(1)
   
2. 
   O’rtacha holatda: n(n+1)/2n = O(n)
   
3. 
   Eng yomon holatda: O(n)
   

Ikkilik qidirish ishlash tezligi:

1. 
   Eng yaxshi holatda: O(1)
   
2. 
   O’rtacha holatda: logn(logn+1)/2logn = O(logn)
   
3. 
   Eng yomon holatda: O(logn)
   

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