Saralash algoritmlarini qiyosiy tahlili
Download 404.33 Kb. Pdf ko'rish
|
RAMZBEK 2
- Bu sahifa navigatsiya:
- 1. Boltayev B.J , Azamatov A.R , Rahimov A.D “Algoritmlash va dasturlash asoslari” kitobi 2. A.M. Po’latov “Algoritmlash va C++ dasturlash asoslari” kitobi
|
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. • 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=2 k -1 deb faraz qilaylik. Agar shunday boʻlsa, ikkinchi oʻtishda nechta element qoladi? Uchinchidachi? Umuman olganda, tushunarliki , agar sikl qandaydir oʻtishda 2 j -1 element roʻyxat bilan ishlasa, u holda roʻyxatning birinchi yarmida 2 j-1 -1 element boʻladi, bitta element oʻrtada va 2 j-1 -1 elementlar roʻyxatning ikkinchi yarmida boʻladi. Shuning uchun keyingi oʻtishga 2 j- 1 -1 element qoladi Foydalanilgan adabiyotlar • 1. Boltayev B.J , Azamatov A.R , Rahimov A.D “Algoritmlash va dasturlash asoslari” kitobi 2. A.M. Po’latov “Algoritmlash va C++ dasturlash asoslari” kitobi 3. A.R. Azamatov “Algoritmlash asoslari” kitobi 4. hozir.org 5. uzvikipediya.org 6. arxiv.uz Download 404.33 Kb. Do'stlaringiz bilan baham: 
|