|
-§. Linear Search(Chiziqli qidirish) algoritmi va uning xossalari
|
| bet | 8/12 | | Sana | 21.05.2024 | | Hajmi | 117,25 Kb. | | #248931 |
Bog'liq 1-kurs kurs ishi(2)
3-§. Linear Search(Chiziqli qidirish) algoritmi va uning xossalari
Linear Search (Chiziqli qidirish) algoritmi ma'lum bir qiymatni tartiblangan yoki tartiblanganmas to'plamda (masalan, massivda yoki ro'yxatda) qidirish uchun ishlatiladi. Ushbu algoritmni bajarish jarayoni quyidagicha:
Boshlang'ich to'plamning boshidan boshlab har bir elementni tekshirish.
Qidirilayotgan qiymatni har bir element bilan solishtirish.
Agar topilgan bo'lsa, elementni indeksini qaytarish.
Agar topilmagan bo'lsa, keyingi elementni tekshirish.
Chiziqli qidirish algoritmi odatda to'plam elementlar sonining eng yomon, yani O(n) vaqtni talab qiladi. Bu algoritmda qidiruv elementi to'plamning boshidan boshlab birinchi elementdan boshlab qo'shig'i barcha elementlarni tekshirish bilan bajariladi. Agar qidirilayotgan qiymat topilsa, indeksi qaytariladi; aks holda, to'plam tugaguncha tekshirish davom ettiriladi.
Lineer qidiruvning afzalliklari: Chiziqli qidiruv massivning tartiblangan yoki tartiblanmaganligidan qat'iy nazar foydalanish mumkin. U har qanday turdagi ma'lumotlar massivlarida ishlatilishi mumkin. Hech qanday qo'shimcha xotira talab qilmaydi. Bu kichik ma'lumotlar to'plamlari uchun juda mos keladigan algoritm.
Lineer qidiruvning kamchiliklari: Chiziqli qidiruv O (N) vaqt murakkabligiga ega, bu esa o'z navbatida katta ma'lumotlar to'plamlari uchun uni sekinlashtiradi. Katta massivlar uchun mos emas. Lineer qidiruvdan qachon foydalanish kerak? Biz kichik ma'lumotlar to'plami bilan ishlayotganimizda. Qo'shni xotirada saqlangan ma'lumotlar to'plamini qidirayotganingizda. Lineer qidiruvning (chiziqli qidiruv) kamchiliklari quyidagilardan iborat:
Past samaradorlik Lineer qidiruv algoritmi har bir elementni ketma-ket tekshirish orqali qidirilayotgan qiymatni topadi, bu esa to'plamning kattaligiga qarab juda ko'p vaqt talab qiladi. O(n) vaqt murakkabligi bu algoritmning katta to'plamlar uchun samarasiz ekanligini bildiradi.
|
| |
