Bajardi: Donayev Islom. Tekshirdi: Eshmuhammedov Aziz. Guruh: cao021 toshkent-2020

O‘ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI
MUHAMMAD AL-XORAZMIY NOMIDAGI

TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI

Yakuniy nazorat ishi

Variant № 9

1. 
   Chiziqli qidirish algoritmining tahlili.
   
2. 
   Ketma-ket qidiruv va indeksli ketma-ket qidiruvlarning qaysi biri samaraliroq va nima sababdan?
   
3. 
   NP bilan bogʼliq muammolarni xal qilish yoʼllari.
   

Bajardi: Donayev Islom.
Tekshirdi:Eshmuhammedov Aziz.
Guruh:CAO021
TOSHKENT-2020
1.Chiziqli qidirish algoritmining tahlili.

Chiziqli qidiruv – bunda berilgan kalit chiziqli ketma ketlikda to’plam elementlari orasidan qidirib chiqiladi. Bu algoritm ancha sodda lekin sekin hisoblanadi.

Intervalli qidirish: Ushbu algoritmlar maxsus ajratilgan ma'lumotlar tuzilmalarida qidirish uchun mo'ljallangan. Ushbu turdagi qidiruv algoritmlari Linear Search-ga qaraganda ancha samaralidir, chunki ular qayta-qayta qidiruv tuzilmasi markaziga yo’naladi va qidiruv maydonini ikkiga bo’ladi. Masalan: Ikkilik qidiruv.

Chiziqli qidirish algoritmi qanday ishlaydi

Aytib o’tganimizdek, bu algoritm juda ham sodda ishlaydi va tasavvur qilishga ham oson.Arrayning birinchi elementidan tekshirish boshlanadi.Element olinadi va u berilgan shartga tekshirib ko’riladi.Agar shartni qanoatlantirsa, uning qiymati yoki joylashgan o’rni (qiymati yoki shunchaki true) qaytariladi va algoritm tugaydi.Shart qanoatlantirilmasa, keyingi elementga o’tiladi va 2-qadamga qaytiladiArray tugab, element topilmasa, buni anglatuvchi qandaydir qiymat qaytariladi (-1 yoki false…)

Ko’rinishidan ko’pdek tuyulsa ham, aslida bu algoritm hayotdagi odatiy qidirish bilan bir xil ishlaydi. Keling uni visual holda tasavvur qilamiz.
Algoritm murakkabligi

Chiziqli qidirish algoritmining vaqt bo’yicha murakkabligi uning nomidan ham ma’lum, ya’ni chiziqli O(n). Ya’ni, eng yomon holat sifatida element array bo’lmagan holat qaraladi va bunda algoritm maksimum n ta qadam ish bajarishi kerak bo’ladi.

Xotira jihatidan, algoritm ortiqcha joy talab qilmaydi.
Chiziqli qidirish algoritmi ko’pincha real hayotdagi holatlar uchun ancha sekinlik qiladi. Shuning uchun ham bunday holatlarda undan boshqa tezroq ishlaydigan algoritmlar qo’llanilishi kerak bo’ladi (masalan, ikkilik qidirish). Lekin, bu algoritmning ham ikkilik qidirishdan o’ziga yarasha avfzal tomonlari mavjud. Bunga ikkilik qidirish (binary search)
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.