Mavzu: Algoritmlar va ma’lumotlarning dastur bilan bog’liqligi Reja

Mavzu: Algoritmlar va ma’lumotlarning dastur bilan bog’liqligi
Reja:
1. Dasturlar murakkabligining tahlili
2. Elementar saralash usullari
3. Tezkor saralash
4. Imtiyozli navbatlar va pyramidal saralash
5. Razriyadlar bo’yicha saralash va izlash


Tayanch iboralar:
Dastur, algoritm, Asimptotik Tahlil, notatsiya, Bubble sort, saralash, tezkor saralash, piramida, navbat, navbat nazariyasi, tartiblash, xotira, turg’unlik


1. Dasturlar murakkabligining tahlili

Dastur tuzish jarayonida uning ko'p taraflariga e'tibor berish kerak: modullilik, qulay interfeyslilik, xavfsizlilik, tushunarlilik va b.q. Dasturningning ishlash davomida o'zini tutishi (performance) esa dasturning barcha muhim jihatlaridanda muhimroqdir. Chunki,dasturni qotib qolmasdan ishlashi va doim to'g'ri natijalar berishi uning asosiy vazifasidir. Dastur uchun eng yaxshi unumdorlikni tanlash uchun esa unda foydalaniladigan algoritmni dastlab Tahlil qilib ko'rish kerak.

Ikkita algoritm berilgan, qaysi biri yaxshiroq ekanligini qanday aniqlash mumkin?
Eng oddiy yo'li, dasturni ikkita kompyuterda ishga tushirib dasturga turli sonlar kiritish bilan tekshirib ko'rish va qaysi birini kam vaqt olayotganini aniqlash. Ammo, bu usulning juda ko'p kamchiliklari mavjud:
1) Ba'zi sonlar uchun birinchi algoritm, ba'zi sonlar uchun esa ikkinchi algoritm tezroq ishlashi mumkin.
2) Ba'zi sonlar uchun birinchi kompyuterdagi birinchi algoritm, ba'zi sonlar uchun esa ikkinchi algoritm boshqa kompyuterda tezroq ishlashi mumkin.
Algoritmni asimptotik Tahlil qilish yuqoridagi muammolarni bartaraf etishga yordam beradi. Algoritmni asimptotik Tahlil qilishda biz algoritmga turli sonlar kiritilganda u qanday unumdorlik ko'rsatishini baholaymiz. Biz algoritmga kiritilayotgan sonlar ortishi bilan uning ishlash vaqti (yoki xotiradan joy egallashi) qanday ortishini o'lchaymiz (algoritmni ishlash vaqt davomiyligi qanchaligini emas).
Asimptotik Tahlil algoritmni baholash uchun eng yaxshi variantmi?
Asimptotik Tahlil 100% to'g'ri tahlil qilish imkonini bermaydi, ammo algoritmini asimptotik Tahlil qilish mavjud boshqa barcha Tahlil yo'llari ichida eng yaxshisi. Misol uchun, ikkita saralash algoritm bor deb tassavur qilaylik, birinchisiga n son kiritilganda uning ishlash vaqti 100nLog(n) funksiya asosida, ikkinchisiga n son kiritilganda uning ishlash vaqti 2nLog(n) funksiya asosida ortsin. Bu algoritmlarning unumdorligi asimptotik Tahlilda teng deb hisoblanadi (o'sish tartibi nLog(n)), chunki asimptotik Tahlilda konstanta koeffisiyentlar hisobga olinmaydi.