1. Asimptotik analiz. Algoritmlarni analiz qilish

Analiz qilishdan maqsad.

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 analiz 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 analiz qilish yuqoridagi muammolarni bartaraf etishga yordam beradi. Algoritmni asimptotik analiz 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 analiz algoritmni baholash uchun eng yaxshi variantmi?

Asimptotik analiz 100% to’g’ri tahlil qilish imkonini bermaydi, ammo algoritmini asimptotik analiz qilish mavjud boshqa barcha analiz 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 analizda teng deb hisoblanadi (o’sish tartibi nLog(n)), chunki asimptotik analizda konstanta koeffisiyentlar hisobga olinmaydi.

Davomi bor…

Manba:

Umarov Islom