|
O‘zbekiston respublikasi oliy ta’lim, fan va innovatsiyalar vazirligi farg‘ona davlat universiteti
|
| bet | 10/12 | | Sana | 21.05.2024 | | Hajmi | 117,25 Kb. | | #248931 |
Bog'liq 1-kurs kurs ishi(2)Javoblari:
1.Chiziqli qidiruv, shuningdek, ketma-ket qidiruv deb ham ataladi, maqsad elementni topish uchun ro'yxat yoki massivni ketma-ket bosib o'tadigan oddiy qidiruv algoritmidir. Chiziqli qidiruvda biz ni olishimiz mumkin
2. Chiziqli qidiruv ro'yxat yoki massivdagi har bir element bo'ylab takrorlanadi va moslik topilmaguncha yoki ro'yxat oxirigacha uni maqsad element bilan taqqoslaydi. Agar ro'yxatning oxirigacha erishilsa, bu maqsad element massivda mavjud emasligini anglatadi.
3. Chiziqli qidiruvning vaqt murakkabligi O(n), bu yerda n - izlanayotgan ro'yxat yoki massivdagi elementlar soni. Bu shuni anglatadiki, qidirish uchun sarflangan vaqt kirish hajmi bilan chiziqli ravishda oshadi.
4. Roʻyxat yoki massiv tartiblanmagan boʻlsa yoki kirish hajmi nisbatan kichik boʻlsa, chiziqli qidiruv afzalroqdir. Amalga oshirish oson va ma'lumotlarning aniq tartibda bo'lishini talab qilmaydi.
5. Chiziqli qidiruvni amalga oshirish oson va u kichik o'lchamli massivlar yoki ro'yxatlarda samarali ishlaydi. Bu saralash kabi oldindan ishlov berishni talab qilmaydi, bu uni dinamik ma'lumotlar tuzilmalari uchun mos qiladi.
6. Chiziqli qidiruv katta o'lchamli massivlar yoki ro'yxatlar uchun samarasiz bo'lib qoladi, chunki u har bir elementni ketma-ket skanerlashi kerak. U O(n) vaqt murakkabligiga ega, ya'ni qidiruv vaqti kirish hajmiga qarab chiziqli ravishda o'sib boradi.
7. Chiziqli qidiruv massiv yoki roʻyxat elementlari boʻylab takrorlash, moslik topilmaguncha yoki roʻyxat oxiriga yetguncha har bir elementni maqsadli qiymat bilan solishtirish uchun halqalar yordamida amalga oshirilishi mumkin.
8. Ha, chiziqli qidiruv nafaqat massivlar yoki ro'yxatlarga, balki bog'langan ro'yxatlar kabi boshqa chiziqli ma'lumotlar tuzilmalariga ham qo'llanilishi mumkin. Printsip bir xil bo'lib qoladi: maqsad topilmaguncha yoki oxiriga yetguncha har bir elementni takrorlash.
9. Chiziqli qidiruv hali ham tartiblangan massivlar yoki ro'yxatlarda ishlatilishi mumkin bo'lsa-da, bu eng samarali variant emas. Ikkilik qidiruv, masalan, saralangan ma'lumotlar uchun ko'proq mos keladi, chunki u vaqt murakkabligi O (log n) ga ega.
10. Chiziqli qidiruv telefon kitobida ma'lum bir qiymatni qidirish, kontaktlarning saralanmagan ro'yxatidan nom qidirish yoki oziq-ovqat ro'yxatidagi elementni topish kabi stsenariylarda ishlatilishi mumkin. U ko'pincha ma'lumotlar hajmi kichik bo'lgan yoki sezilarli darajada o'sishi kutilmaydigan stsenariylarda qo'llaniladi
Chiziqli qidirish algoritmi quyidagi xossalarga ega:
Oddiylik: Bu algoritm yomonlik qidirishga nisbatan juda oddiy va sodda hisoblanadi. Elementlar to'plamining o'lchami bilan mos ravishda tekshiriladi.
|
| |
