Linear Search

Vaqt murakkabligi nima ekani haqidagi umumiy tushuntirish uchun ushbu sahifaga qarang.

Chiziqli qidiruvning vaqt murakkabligi

Vaqt murakkabligi nima ekanligi haqida umumiy tushuntirish uchun ushbu sahifaga tashrif buyuring.

Insertion Sort vaqt murakkabligi haqida yanada chuqurroq va batafsil tushuntirish uchun ushbu sahifaga tashrif buyuring.

Chiziqli qidiruv (Linear Search) har bir qiymatni qidirilayotgan qiymat bilan taqqoslaydi. Agar qiymat topilsa, uning indeksi qaytariladi, topilmasa -1 qaytariladi.

Linear Search vaqt murakkabligini topish uchun \(n\) ta qiymatli massivda qiymatni topish uchun nechta taqqoslash amali kerakligini aniqlashga harakat qilaylik.

Eng yaxshi holat — qidirilayotgan qiymat massivdagi birinchi qiymat bo‘lishi. Bunday holatda faqat bitta taqqoslash kerak bo‘ladi va vaqt murakkabligi \(O(1)\) ga teng.

Eng yomon holat — maqsadli qiymat topilmasdan butun massiv ko‘rib chiqilishi. Bunday holatda massivdagi barcha qiymatlar maqsadli qiymat bilan taqqoslanadi va vaqt murakkabligi \(O(n)\) ga teng.

O‘rtacha holatni aniq belgilash unchalik oson emas. Maqsadli qiymatni topish ehtimoli qanday? Bu massivdagi qiymatlarga bog‘liq, shunday emasmi? Ammo massivdagi qiymatlardan aynan bittasi maqsadli qiymatga teng va bu qiymat istalgan joyda bo‘lishi mumkin deb faraz qilsak, Linear Search uchun kerak bo‘ladigan o‘rtacha vaqt eng yomon holatda kerak bo‘ladigan vaqtning yarmiga teng.

Linear Search vaqt murakkabligi \(O(n)\) ga teng.

Agar chiziqli qidiruvga \(n\) ta qiymatli massivda qiymatni topish uchun qancha vaqt kerakligini chizsak, quyidagi grafikni olamiz:

Linear Search simulyatsiyasi

Simulyatsiyani massivdagi turli miqdordagi qiymatlar uchun ishga tushiring va Linear Search \(n\) ta qiymatli massivda qiymatni topishi uchun nechta taqqoslash kerakligini ko‘ring:

Linear Search simulyatsiyalarini ishga tushirganda ko‘rganingizdek, qiymat tez topilsa, qidiruv uchun kam taqqoslash kerak bo‘ladi, ammo qidirilayotgan qiymat topilmasa, maksimal miqdordagi taqqoslashlar bajariladi.