Algoritmlar texnologiya sifatida. Samaradorligi Algoritmlar va boshqa texnologiyalar

2-MAVZU: ALGORITMLAR SAMARADORLIGINI BAHOLASH


Reja

1. 
   Algoritmlar texnologiya sifatida.
   
2. 
   Samaradorligi
   
3. 
   Algoritmlar va boshqa texnologiyalar
   

Algoritmlar texnologiya sifatida.
Kompyuteringizning tezligi va xotira miqdorini abadiy oshirish mumkin, deylik. Bu holatda algoritmlar o’rganish kerakmi? Bor bo'lishi mumkin, lekin faqat namoyish etish uchun, echim usulini cheklangan vaqti bor va u to'g'ri javob beradi.
Kompyuterlar juda tez bo’lganda, masalani echishga har qanday konkret usul mos kelarmidi.
Albatta, bugungi kunda juda samarali kompyuterlar, lekin ularning ishlashi juda katta bo'lishi mumkin emas. Xotira ham arzon, lekin bepul bo'lishi mumkin emas. Shunday qilib, hisob-vaqti - cheklangan resurs, shuningdek xotira miqdori ham. Siz donolik bilan bu resurslarini boshqarishingiz kerak,bunga algoritmlardan, vaqt va xotira xarajatlaridan samarali foydalanish kerak.
Samaradorligi
Har xil masalalarni yechish uchun mo'ljallangan, turli xil algoritmlar, samaradorligi bo'yicha sezilarli darajada farq qiladi. Bu farqlar juda katta bo'lishi mumkin ekan. Masalan, ikki saralash algoritmlar, 2-darsta muhokama qilinadi. Birinchisini bajarish uchun, saralashni joulashtirish, bunga vaqt kerk bo’ladi, shunday baxolanmoqda c₁n² , n- bu saralash elementlarning soni, c₁ bo’lsa bu – doimiy, n ga bog’liq emas. Shunday qilib, bu algoritmni vaqti taxminan n2 proportsional.
Ikkinchi algoritm amalga oshirish uchun, saralash birlashtirishi, vaqt talab etadi, taxminan c₂n lg n ga teng, lg n- bu log₂ n qisqa yozuvi, c₂ bu - boshqa doimiy n ga bog’liq emas.Odatda doimiy usul qo'shimchalar doimiy birlashish usulidan kichikroq, c₁ < c₂. Doimiy omillar algoritmni ish vaqtiga juda kan ta’sir qiladi,n ga bog'liq omillardan ko’ra, shunga ishonch xosil qilaylik.Saralashni joylashtirish algoritmni ish vaqtini shunday yozaylik c₁ n n,birlashtirish saralashini esa c₂n lgn.
Joylashtirish saralashi n omilga ega, birlashtirish saralashi esa lg n ga ega bu esa sezarli darajada kamligini ko’rishimiz mumkin.Kiritish hajmi n etarlicha katta bo'lganda qo'shish saralashi odatda tezroq bo’ladi, saralash ob'ektlar kichik hajmdagi birlashtirishda, katta n uchun ahamiyatsiz qiymati lgn nisbatan n to'liq doimiy farqi qadriyatlar o'rnini qoplash, aslida birlashish yanada sezilarli namoyon bo’ladi, saralash afzalligi ziyoda.Bu doimiy c₁, c₂ dan necha marta kam muhim emas.Saralash elementlarini sono ishshi bilan burilish nuqtasi hosil bo’ladi,shunda birlashish saralashi yanada samarali bo'ladi.
Misol tarzida ikkita A va B kompyuterlarni ko’rib chiqamiz.A kompyuteri ancha tezroq, va unda joylashtirish saralashi algoritmi ishlaydi, B kompyuter esa sekin va unda saralash algoritmi birlashtirish usuli bilan ishlaydi.Har ikkita kompyuterlar bir nechta saralashni bajarishi kerak.Kompyuter A sekundiga o'n milliard ko'rsatmalar bajaradi, B kompyuter sekundiga faqat o'n million ko'rsatmalar bajaradi,shuhday qilib A kompyuteri ming marta B kompyuterdan tez. Saralash birlashishi yuqori darajadagi til yordamida bir programct tomonidan amalga oshirilgan.
Bu kompilyator juda samarali emas edi, va natija 50n lg n ko'rsatmalarga bajaradigan kod paydo bo’ldi.

O'n million raqamlarini tartiblashtirish uchun A kompyuterga kerak bo’ladi:

B kompyuterga kerak bo’ladi

Ko'rib turganingizdek, kod bilan foydalanish, ish vaqti sekin ko’tarilganda,yomon komilyator bilan ham eng sekin kompyuterda ham17 marta kam vaqt talab qiladi.

Qo’shish usuli joylashtirish usulidan samaraliroq ekanligini quyida keltirilgan jadlal ma’lumotlarini tahlili orqali keltiramiz.

komputerlar	Saralanadigan sonlar soni	Saralovchi algoritm	Talab qilinadigan vaqt
A(tez ishlovchi 1sekundda 10mlrd amal bajaradi)	10 mlnta (taqriban 80 mb)	Joylashtirish usuli (tajribali dasturchi tomonidan yaratilgan algoritm saralash uchun 2n^2amal bajariladi)	=20000 sec (5,5 soatdan ko’proq)
B(sekin ishlovch- 1sekundda 10 mln amal bajaradi)		Qo’shish usuli (o’rta darajali dasturchi tomonidan yaratilgan algoritm saralash uchun 50nlgnamal bajariladi))