Asimptotik analiz. Kirish
Aytaylik uyingizni ta’mirlamoqchisiz, ustani olib keldiz. Ishlarni qisqacha tushuntirganizdan so’ng ustadan so’raydigan savolingiz, barcha ishni tugatishga qancha vaqt ketishi va xizmat xaqi nech pul bo’lishi haqida bo’ladi. Javobga qarab boshqa usta olib kelasiz yoki qimmatbaho qandil osishni kechiktirasiz. To’g’rimi?
Endi xuddi shu muammoni algoritmlarga ko’chiraylk. Biror bir muammoni hal qilishga mo’ljallangan algoritm yozayotganizda uning qanchalik tez va xotirani qay darajada band qilishini oldindan bilmoqchi bo’lasiz. Boshqacha qilib aytganda, o’ylab topganiz dunyoda yagona algoritmni samaradorligi haqida bosh qotirasiz. Demak algoritmlarni analiz qilish haqida so’z yuritamiz. E’tiborimizni asimptotik analiz nomi bilan ma’lum bo’lgan uslubga qaratamiz. Bugun maqolani ushbu usulga kirish sifatida qabul qilasiz.
Bir muammoni hal qilishga mo’ljallangan ikki algoritmni qaysi biri samaraliroq ekanligini qanday aniqlanadi. Hayolingizga keladigan dastlabki fikr «Ikkalasini ham kodga aylantirvolib, keyin ularni vaqt va resurs bo’yicha o’lchayman!» bo’lishi mumkin. Lekin, xech bo’lmaganda to’rt sababga ko’ra bu usul eng ma’qul usul emas.
Birinchidan, faqatgina bir algoritmga muxtojsiz, ikkalasini ham kodga aylantirishga umuman vaqtingiz yo’q.
Ikkinchidan, ikkita algoritmni solishtirayotganizda biri ikkinchisidan sifatliroq yozilganlik xavfi bor. Har holda dasturchining qo’li qayeridan o’sganligiga ham ko’p narsa bo’gliq.
Uchinchidan, siz tanlagan test parametrlar u yoki bu algoritm foydasiga xizmat qilib qo’yishi mumkin.
To’rtinchidan, ikkala algoritm ham sizning cho’ntagizga to’g’ri kelmasligi mumkin, natija esa ikkalasi ham keraksiz matoxdek.
Bunday bosh og’riqdan qochishning yaxshi usullaridan biri bu
Asimptotik analizusulidir. Algoritmlar uchun eng muhim o’lchov bu vaqtdir, lekin faqat vaqtning o’zi bilan kifoyalanish ham yaxshi emas, shu sabab odatda biz algoritm uchun sarflanadigan vaqtni va xotiradan egallaydigan hajmni taxlil qilamiz. Vaqt bu algoritmni ichidagi operatsiyalar uchun mezon bo’lsa, hajm algoritm uchun kerak bo’lgan ma’lumotlar strukturasi egallaydigan joy uchun mezon.
Agar algoritmning ishlash vaqtini chuqurroq tushunishni xoxlasak, boshqa faktorlarga ham e’tibor berishimiz lozim. Masalan, kompyuterning ishlash tezligi, dasturlash tilining o’ziga xosliklari, kompilyator va boshqalar. Bizning holatda, hamma narsani ideal deb qabul qilib olamiz.
Demak, algoritmni samadorligini o’lchashda, algoritm bajaradigan
oddiy operatsiyalarsoni va qayta ishlanadigan kiruvchi parametrlarni hajmiga tayanamiz. Masalan, qo’shish, ayirish, taqqoslash va boshqa amallar «oddiy operatsiya» deyiladi. Massiv elementlarini umumiy yig’indisi esa oddiy amal emas sababi, uning qiymati massivni o’lchami ya’ni ga bog’liq. Saralash algoritmlaridagi, saralanishi lozim bo’lgan massivning o’lchami esa bu «hajm».
/**a massivdagi eng katta element joylashgan indeksni qaytaradi.**/
public static int Max(int[] a)
{
int max = 0;/// eng katta element joylashgan indeks
for (int i = 0; i /// massivning Har bir elementi
{
if (a[max] ///agar a[i] katta bo’lsa
max = i;
///uning o’rni yangi qiymat sifatida qabul qilinadi.
}
return max;/// eng katta qiymatni qaytaramiz.
}
Yuqorida berilgan kod parchasida massivning ichidan qiymati eng katta bo’lgan elementni qaytarish muammosi hal qilingan.
a.Length bu a massivdagi elementlar soni. Ya’ni n . Aytaylik, taqqoslash va o’zlashtirish amallari — amal qilinish vaqti bir xil c konstantaga teng bo’lgan oddiy amallar. Demak, bu algoritm ishlash vaqtini asosan foramali egallaydi. Algoritmning ishlash vaqti T bo’lsin. Bundan kelib chiqadi:
T(c)=cn
Bu formula massivning eng katta elementini topish algoritmining
o’sish darajasideyiladi.
Keling endi e’tiborimizni quyidagi kod parchasiga qaratamiz.
int sum = 0;
for (int i = 0; i
{
for (int j = 0; j
{
sum++;
}
}
Xo’sh buning ishlash vaqti qanaqa? Oddiy operatsiya bu-
sumning qiymatini bittaga oshirish. Buning ishlash vaqtini ham c konstanta deb qabul qilib olaylik. Demak yana eng ko’p vaqt for uchun ketadi. Kod parchasidan shuni anglash qiyin emaski, oddiy amalimiz n^2 marta bajariladi. Bu algoritmning o’sish darajasi:
T(n) = cn^2
Ikki algoritmning o’sish darajasiga qarab qaysi biri tezroq ishlashini bemalol ayta olamiz. Quyidagi jadvalda komputer algoritmlari orasida eng ko’p tarqalgan o’sish darajalari berilgan.
Do’stim, demak siz endi u yoki bu algoritmni o’rganayotgan vaqtingizda ularning o’sish darajasiga qarab qaysi biri tezroq ekanligini bemalol ayta olasiz. Endi sizga savol:Aytingchi, tezkor kompyuter yaxshimi? yoki tezkor algoritm? Javoblaringizni izoh ko’rinishida qoldiring.
Manba:
Algoritm
Asimptotik analiz. Kirish