|
O‘zbekiston respublikasi oliy ta’lim, fan va innovatsiyalar vazirligi farg‘ona davlat universiteti
|
| bet | 7/12 | | Sana | 21.05.2024 | | Hajmi | 117,25 Kb. | | #248931 |
Bog'liq 1-kurs kurs ishi(2)Sodda qo'llanish: Algoritm sodda va oson hisoblanadi. Har bir solishtirishda faqatgina bir necha solishtirish amallari bajariladi, shuningdek solishtirishlarning soni logarifmik bo'lgani uchun, barcha solishtirishlar jami, o'lchamning o'lchami bilan mos keladi.
Balandlik: Bu algoritm faqatgina tartiblangan to'plamlarda ishlaydi. Agar to'plam tartiblanmagan bo'lsa, avval uni tartiblash kerak bo'ladi, bu esa O(n log n) vaqtni talab qiladi.
Oddiylik: Binary Search algoritmi yomonlik qidirishga nisbatan odamiy va sodda algoritm hisoblanadi. Uning implementatsiyasi oson va juda tushunarli.
Tartiblangan ro'yxat: Ikkilik qidirish algoritmi faqat tartiblangan ro'yxatlarda ishlaydi. Agar ro'yxat tartiblangan bo'lmasa, algoritm noto'g'ri natija beradi.
Effektivlik: Ikkilik qidirish algoritmi har bir jihatdan arzon vaqt va zaxira operatsiyalarni bajaradi. Uning vaqt complexitysi O(log n) bo'ladi (n - ro'yxatdagi elementlar soni).
O'rta elementni solishtirish: Algoritm har safar o'rtadagi elementni solishtirib, izlangan qiymatni iltimos bo'lgan safarga bog'langan odamlar yuzaga chiqishi mumkin bo'lgan shaklga o'rnatsa, vaqt complexitysi azaladi.
Bir necha solishtirishlar: Agar izlangan qiymat ro'yxatda mavjud bo'lmasa yoki bir nechta bir xil qiymatlarga ega bo'lsa, ikkilik qidirish algoritmi natijani topmaydi
Binary Search algoritmi, odatda tartiblangan to'plamlarda bir elementni qidirish va topish uchun yaxshi ishlaydi. Ushbu algoritmning qo'llanishi, tezligi va sodda qo'llanishi sababli, keng qo'llaniladi va xususan dasturlashda yaxshi o'lchamli qidiruvni bajarish uchun tavsiya etiladi.
Ikkilik qidirish algoritmining ishlashini tushunish uchun kompyuter bilan oʻyin oʻynab koʻramiz.
Oʻyin sharti
Kompyuter 1 va 100 oraligʻida ixtiyoriy natural son tanlaydi.
Oldimizda turgan vazifa shu sonni iloji boricha kam taxmin ishlatgan holda topish.
Har bir taxmindan keyin kompyuter sizga sizning taxminingiz kompyuter tanlagan sondan katta yoki kichikligini aytadi.
Agar sizning taxminingiz kompyuter tanlagan son bilan bir xil boʻlsa, oʻyin tugaydi.
Buning uchun eng kam qadamda topish algoritmi qaysi?
Birinchi navbatda oʻrtadagi sonni taxmin qilib koʻramiz, yaʼni 50 ni. Aytaylik kompyuter bizga taxminimiz kompyuter tanlagan sondan kichikroq ekanligini aytdi. Endi biz kompyuter tanlagan son 51 va 100 orasidagi son ekanligini bilamiz. Shunday qilib, bizning qidirish sohamiz ikki baravarga qisqaradi (50 ta son). Huddi shu tarzda davom etamiz. Endi 51 dan 100 gacha sonlar oʻrtasidagi sonni olamiz, yaʼni 75 ni. Kompyuter bizga 75 tanlangan sondan katta ekanligini aytdi. Demak, 75 dan katta barcha sonlar ham tanlangan sondan katta ekan. Shunday qilib, bizdagi qidirish sohasi yana ikki baravarga qisqardi (25 ta son). Huddi shunday davom etib, biz oʻylangan sonni topishimiz mumkin. Sonlar 100 ta boʻlgan holatda, biz har qanday tahminni koʻpi bilan 7 ta qadamda topishimiz mumkin boʻladi.
|
| |
