Mavzu: Algoritmlar samaradorligini tahlil qilish. Reja: Samaradorlik ko’rsatkichlari

Bu yerda vaqtli qiyinlik – bu n kattalikdagi kirishlarni qayta ishlash uchun kerak bo’ladigan vaqt birliklar soni. Masalan, vaqt birligini 1 millisekund deb qabul qilaylik. Bunda A1 algoritm bir sekundda 1000 kattalikdagi kirishni qayta ishlash mumkin, A5 algoritmi esa kirish kattalikdagina 9 dan oshirib bilmaydi. Keyingi jadval 1 sekundda, 1 minutda, 1 soatda 5 ta algoritmlarni har birining yordamida yechiladigan masalaning kattaligi keltirilgan.

Faraz qilaylik, keyingi avlod hisoblash mashinalari birinchi jadvalga nisbatano’n barobar tezligi oshadi. Keyingi jadvalda shunday oshishga nisbatan yechiladigan masalalar kattaligining oshishi ko’rsatilgan.

Bu yerda A5 algoritm uchun tezlikni 10 barobar oshishi masalaning kattaligining uchga oshishiga olib keladi. A3 algoritm esa kattalik uch barobardan ziyod oshadi. Endi, tezlik oshishining o’rniga algoritmni kiruvchi berilganlarning hajmini oshishini ko’ramiz. Birinchi jadval bo’yicha taqqoslash asosi sifatida 1 min.ni qabul qilsak, A4 algoritm o’rniga A3 ni qo’llaganimizda, masalaning kattaligi 6 barobar oshadi, A4 algoritmni o’rniga A2 ni qo’llaganda esa 125 barobar oshirilishga erishamiz Agar taqqoslash asosi sifatida 1 soatni qabul qilsak, natijalar yanada ham muhimlashadi. Algoritm va uning qiyinligini batafsilroq muhokama qilish uchun biz algoritmni amalga oshirish uchun qo’llaniladigan hisoblash qurilmalarning modelini va hisoblashning elementar qadamini aniqlashimiz zarur. Afsus-ki, sharoitlarga mos keladigan modelni o’zi yo’q. Eng katta qiyinchilikni mashina so’zlarining kattaliklari tug’diradi. Masalan, agar mashina so’zi ixtiyoriy uzunlikda butun son shaklini qabul qilsa, unda butun masalaning kodi mashina so’zi ko’rinishdagi bir son bo’lishi mumkin. Lekin mashina so’zining uzunligi cheklangan bo’lsa, unda masalaning kattaligi kamroq bo’lganda muammolar yechilsa ham, oddiy katta sonlarni xotiralashda qiyinchiliklar tug’ilishi mumkin.

Ko’plab muammolarda uchraydigan yana bir xususiyat – bu ularning asosan diskretligi. Ko’plab muammolarda uchraydigan yana bir xususiyat-bu ularning asosiy ajralib turishi. Boshqacha qilib aytganda, bu shunday masalalarki, ularda yechim kombinatorial variantlarning keng to’plamidan qidirib topiladi; maqsad aniq belgilangan shartlarni qanoatlantiradigan echimni samarali topishdir.