2-MAVZU: ALGORITMLAR SAMARADORLIGINI BAHOLASH

 

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, yechim usulini cheklangan vaqti bor va u to'g’ri javob beradi. Kompyuterlar juda tez bo’lganda, masalani yechishga 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 olsak, birinchisini bajarish uchun, saralashni joylashtirish, bunga vaqt kerak bo’ladi, shunday baholanmoqda 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 katta 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 yetarlicha 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, shunday qilib A kompyuteri ming marta B kompyuterdan tez. Saralash birlashishi yuqori darajadagi til yordamida bir dasturchi tomonidan amalga oshirilgan. Bu kompilyator juda samarali emas edi, va natija 50nlgn ko'rsatmalarga bajaradigan kod paydo bo’ldi.

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

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

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

Algoritmlar va boshqa texnologiyalar

Yuqoridagi misol shuni ko’rsatadiki, kompyuter apparat kabi algoritmlarni ham, texnologiya sifatida hisobga olinishimiz kerak.

Umumiy tizim ish faoliyatini algoritm samaradorligiga ham bog’liq, va apparat kuchiga ham. Algoritm rivojlantirish sohasida jadal rivojlantirish bo’lyapti, boshqa kompyuter texnologiyalaridek.

Savol tug’iladi, algoritmlar shunchalik muhimi, zamonaviy kompyuterlarda ishlaydigan bo'lsin, agar shunday kabi yuqori texnologiyalar boshqa sohalarda ulkan yutuqlarga erishilgan bo'lsa:

• zamonaviy kompyuter mimarileri va ularning ishlab chiqarish texnologiyalari;

• osonlik bilan erishish, intuitiv grafik foydalanuvchi interfeysi (GUI);

• Ob'ektga yo'naltirilgan tizimlar;

• Integratsiyalashgan veb texnologiyasi;

• tezroq tarmoqlari, simli va simsiz. [1]

Misol uchun, bir joydan boshqasiga olish uchun qanday belgilaydigan Web xizmat. Uni amalga oshirish bir yuqori samarali apparat, grafik foydalanuvchi interfeysi, bir global tarmoq va, ehtimol, bir ob'ekt yo'naltirilgan yondashuv yotadi.

Bundan tashqari, bunday yo'nalishlarini topish kabi bir berilgan web-xizmati tomonidan amalga muayyan operatsiyalar uchun zarur algoritmlarni foydalanish, ko'rish va enterpolasyon manzilini, xaritalar bilan foydalaniladi. Bundan tashqari, dastur, yuqori saviyada algoritmik mazmunini talab qilmaydi, kuchli algoritmlarga bog’liq. Bu dastur ishlash apparat ishiga bog’liq ekanligi ma'lum, va amaliy rivojlanishida turli algoritmlardan foydalaniladi.

Biz hammamiz bilamizki, ilova yaqindan grafik foydalanuvchi interfeysi bilan bog’liq, va har qanday grafik foydalanuvchi interfeysini ishlab chiqish uchun talab algoritmlari kerak bo'ladi. Tarmoq ustida ishlaydigan ilovalarni eslatib o'tamiz.

Ular faoliyat olib borishlari uchun, algoritmlarga asoslanga yo’nalishni olib borishlari kerak bo'ladi. Eng keng tarqalgan dasturlar tilda tuziladi, mashinadan farqli. Ularning kodi turli kompilyator va interpretatorlar bilan ishlov beriladi, turli algoritmlardan keng foydalanadi. Bundan tashqari, kompyuterlar kuchini doimiy o'sishi, ular tobora murakkab vazifalarni hal qilish uchun qo'llaniladi. Biz muammoni murakkabligini ortishimiz bilan, ikki saralash usullari qiyosiy tahlili misolida ko'rib turganimizdek eng muhim farqlar algoritmlarini samaradorligini ko'rinadi oshirilmoqda. Asosiy algoritmlar va ularni rivojlantirish usullari-asosiy xususiyatlatdan biri. Zamonaviy kompyuter texnologiyalari bilan, ayrim vazifalarni algoritmlarni bilmagan holda ham qilinishi mumkin, lekin bu sohada kop narsaga erishish mumkin.

Mashqlar

1.2.1 Dastur darajasida zarur bo’lgan algoritmik content dasturini misol qilib keltiring va bu algoritmlarni funksiyasini muhokama qiling.

1.2.2 Deylik, bitta mashinada ikkita saralash algoritmni qiyosiy tahlil amalga oshirilmoqda. N elementlarni joylashtirish saralashi uchun 8n² kerak bo’ladi, birlashtirish saralashi uchun 64n lg n qadamlar kerak bo’ldi. Joylashtirish saralashi birlashtirish saralashidan qiymati oshsa, n ni qiymati qancha bo’lishi kerak?

1.1.          Algoritmlarni ish vaqtini solishtirish

Quyida bir jadval bo'lib, satrlari turli vazifalarga mos f(n), ustunlaru esa- vaqt qiymatiga t. N ni maksimal qiymatlari bilar jadvalni to’ldiring, masala t vaqti bilan yechilishi mumkin, agar masalani yechish uchun algoritmni ish vaqti  f(n)mikro sekundga teng bo’lsa.

 

---

[1] Thomas H. Cormen   va b.  Intruduction to algorithms. Massachusetts Institute of Technology. London 2009.  (11-13рр)