|
Referat mavzu: Saralash algoritmlarining samaradorligi va qiyosiy tahlili. Bajardi: Omonboyev Rashidbek
|
| bet | 3/5 | | Sana | 21.12.2023 | | Hajmi | 17,17 Kb. | | #125752 | | Turi | Referat |
Bog'liq Referat mavzu Saralash algoritmlarining samaradorligi va qiyosi-fayllar.org (2)3.Ikkilik daraxt boʻyicha qidirish
Maqsad qiymatni saralangan roʻyxatning oʻrtadagi qiymati bilan solishtirish uch xil natija berishi mumkin: qiymatlar teng, maqsad qiymati roʻyxat elementidan kichik va maqsad qiymati roʻyxat elementidan katta. Birinchi va eng yaxshi holda qidirish tugaydi. Qolgan ikki holda roʻyxat yarmini tashlab yuborishimiz mumkin.
Agar maqsad qiymati oʻrta elementdan kichik boʻlsa, u holda u bu oʻrta element oldida joylashgan boʻladi. Agar u oʻrta elementdan katta boʻlsa, u holda u oʻrta elementdan keyin joylashgan boʻladi. Bu roʻyxat yarmini tashlab yuborishga yetarlicha sabab boʻladi. Bu jarayonni takrorlab biz roʻyxatning qolgan qismlarini yarmini tashlab yuborishimiz mumkin. Natijada quyidagi algoritmga kelamiz:
BinarySearch(list,target,N)
list ko’rilayotgan ro’yxat
target maqsad qiymati
N ro’yxat eleamentlari soni
start=1
end=N
while start<=end do
middle=(start+end)/2
select(Compare(list[middle],target)) from
case -1: start=middle+1
case 0: return middle
case 1: end=middle-1
end select
end while
return 0
Bunda Compare(х,у) funksiyasi -1, 0 yoki 1 qiymatlarni mos holda xy shartlarda beradi. Algoritmlar tahlilida Compare funksiyani chaqirish bir solishtirish deb hisoblanadi.
Ushbu algoritmda agar maqsad qiymat topilgan oʻrta elementdan katta boʻlsa start oʻzgaruvchi middle qiymatidan 1 ga oshiqqa ta’minlanadi. Agar maqsad qiymat topilgan oʻrta elementdan katta boʻlsa end oʻzgaruvchi middle qiymatidan 1 ga kamga ta’minlanadi. Silijish 1 esa oʻrta element izlanayotgan qiymatga teng boʻlmagan hol bilan tushuntiriladi.
Sikl har doim toʻxtaydimi? Agar maqsad qiymat topilsa buni return operatori ta’minlaydi. Agar kerakli qiymat topilmasa, u holda har bir sikl iteratsiyasida yo start ning qiymati oshadi yo start oʻzgaruvchining qiymati kamayadi. Bu ularning qiymati bir biriga yaqinlashishini koʻrsatadi. Qandaydir vaziyatda ular tenglashadi va sikl start=end=middle da yana bir bor bajariladi. Bu oʻtishdan keyin (agar qidirilayotgan element ushbu indeksga mos kelmasa) yo start qiymati middle va end lardan 1 ga katta boʻladi, yo teskarisi, end oʻzgaruvchi middle va start lar qiymatidan 1 ga kam boʻladi. Ikki holatda ham sikl while yolgʻon boʻladi va sikl boshqa bajarilmaydi. Shu tufayli sikl har doim toʻxtaydi.
Algoritm har doim roʻyxatni yarimga boʻladi va biz tahlilda qandaydir k uchun N=2k-1 deb faraz qilaylik. Agar shunday boʻlsa, ikkinchi oʻtishda nechta element qoladi? Uchinchidachi? Umuman olganda, tushunarliki, agar sikl qandaydir oʻtishda 2j-1 element roʻyxat bilan ishlasa, u holda roʻyxatning birinchi yarmida 2j-1-1 element boʻladi, bitta element oʻrtada va 2j-1-1 elementlar roʻyxatning ikkinchi yarmida boʻladi. Shuning uchun keyingi oʻtishga 2j-1-1 element qoladi(1Eng yomon holat tahlili
Yuqorida koʻrdikki, roʻyxatning qolgan qismlarida barcha oʻtishda ikkining darajalari birga kamayadi. Yana siklning oxirgi iteratsiyasi qolgan qism oʻlchami 1 ga teng boʻlganda bajariladi. Bu esa j=1(ya’ni 21-1=1) da bajariladi. Bu shuni ko’rsatadiki, N=2k-1 da o’tishlar soni k dan oshmaydi. Oxirgi tenglikdan eng yomon holda o’tishlar soni k=log2(N+1) ga tengligini topamiz.
Tahlilda qidirish jarayoni uchun yechim daraxti ham yordam berishi mumkin. Yechim daraxti tugunlarida mos oʻtishda tekshiriladigan elementlar turadi. Yetti elementdan iborat roʻyxat uchun yechim daraxti 2-rasmda keltirilgan. Umumiy holda daraxt nibatan balanslashtirilgan, ya’ni biz har doim roʻyxat turli qismlarining oʻrtasini tanlaymiz. Shuning tufayli solishtirishlar sonini sanash uchun binar daraxtlar uchun keltirilgan formulalardan foydalanamiz.
Madomiki biz N=2k-1 deb faraz qilarkanmiz mos keluvchi yechim daraxti doim to’liq bo’ladi. Unda k daraja, ya’ni k=log2(N+1) bo’ladi. Biz har qaysi darajada bittadan solishtirish bajaryapmiz, shuning uchun solishtirishlar umumiy soni log2(N+1) dan oshmaydi.
2-rasm. Yetti elementli ro’yxatda qidirish uchun yechim daraxti
|
| |
