Mavzu: Algoritmlarni vaqt bo’yicha va hajmiy murakkabligini baholash uchun tekis va logarifmik baholash usullari

1 ni qo‘sh
TAKRORLANSIN 16 MARTA
1 ni qo‘sh
TAMOM
Endi bu algoritmning samaradorligi 17 ga, murakkabligi esa 17 emas, 3 ga teng. Askarlar va qayiq masalasi algoritmida 60 ta askarni daryodan o‘tkazish uchun 240 qadam bajariladi, algoritm matni esa 5 satrdan iborat. Bu algoritmning samaradorligi 240 ga, murakkabligi esa 5 ga teng. Baqa uchun tuzilgan “Baqa toq sondagi n ta bargli nilufarning 1 tartib raqamli bargiga tushdi. U barcha pashshalarni yeb 2 tartib raqamli barg ustiga borish algoritmini tuzing.” masalani algoritmida qadamlar sonini hisoblaymiz:
son + 1 + son — 1 = (n —1):2 + (n — 1):2 = n — 1.
Demak, har qanday n toq son uchun algoritmni samaradorligi n - 1 ga teng ekan. Algoritmning murakkabligi esa n toq son nechaga teng bo‘lishidan qat’iy nazar, 5 ga teng bo‘ladi!
Xulosa. Baqa masalasiga oid algoritmlarning samaradorligi faqat n sonining qiymatiga bog‘liq. Chunki masala shartida Baqa har bir bargdagi pashshani yeb chiqishi talab qilinadi. U holda barglar soni n ta ekanligi va Baqa biror bargning ustida turgandan keyin harakat boshlanganligidan qadamlar soni doimo n-1 ta bo‘lishi kelib chiqadi.
Haqiqatan, masalan, agar 1 tartib raqamli bargdan 4 tartib raqamlibargga o‘tish кегак bo‘lsa, u holda barcha imkoniyatlarni 1.1—1.2-rasmlarda, agar 1 tartib raqamli bargdan 5 tartib raqamli bargga o‘tish kerak bo‘lsa, u holda barcha imkoniyatlarni 1.3—1.5-rasmlardan ko‘rishimiz mumkin.




1.1-rasm




1.2-rasm





1.3-rasm

1.4-rasm




1.5-rasm
Va nihoyat, yana bir izoh. Samaradorlik va murakkablik talabi ko‘pincha bir-biri bilan ziddiyatga kirishadi. Bu mutlaqo tabiiy. Axir, mashina sotib olayotgan bo‘lsangiz, eng chiroyli va qulay mashinaning eng arzon bo‘Iishiga umid qilmaysiz. Algoritmlashda ham shunday. Agar sizga juda samarador algoritm kerak bo‘lsa, bu algoritm boshqalariga nisbatan ancha murakkabroq bo’lishi ehtimoli katta. Amaliyotda esa oqilona murosaga kelishga to ‘g‘ri keladi.

Hisoblash qobiliyati. 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.
Hisoblash samaradorligi tushunchasini aniqlash uchun, biz birinchi navbatda ish vaqtining samaradorligiga e'tibor qaratamiz: algoritmlar tez ishlashi kerak. Ammo algoritmlar boshqa resursrlardan foydalanish nuqtai nazaridan ham samarali bo'lishi mumkinligini tushunish muhimdir. Xususan, algoritm tomonidan ishlatilinadigan xotira miqdori ham samaradorlikning muhim jixati bo'lishi mumkin.
Algoritm samaradorligi. (1)T: algoritm samarali deb ataladi agar real kirish ma'lumotlari uchun u tezkor amalga oshirilsa.
(2)T: algoritm samarali deb ataladi agar u sifatli bajarilishni “to’liq qidirish”(полнiy перебор)ga nisbatan tezroq ta'minlasa.
"To'liq qidirish" usuliga qaraganda ancha yaxshi ishlashni ta'minlaydigan algoritmlar, deyarli har doim qimmatli evristik g'oyani o'z ichiga oladi, buning natijasida ushbu yaxshilanishga erishiladi; Bundan tashqari, ular ko'rib chiqilayotgan masalaning ichki tuzilishi va hisoblash qobiliyati haqida foydali ma'lumotlarni taqdim etadilar.
Polinomial vaqt samaradorlik ko'rsatkichi sifatida. Tabiiy kombinatorial masalalarda qidirish vaqti, kirish ma'lumotlari N hajmiga nisbatan eksponensional o'sishga moyildir; agar o'lcham bittaga ko'paysa, unda imkoniyatlar xajmi bir necha marta ko'payadi. Bunday masalalarni yechish uchun yaxshi algoritm yanada samarali miqyoslash modeliga ega bo'lishi kerak; kirish ma'lumotlarining kattalashib borishi bilan o’zgarmas ko’paytuvchiga(aytaylik, ikki baravar) oshishi bilan algoritmning bajarilish vaqti ham qandaydir o’zgarmas S ko’paytuvchiga ko'payishi kerak.
(3)T: Agar algoritm polinomial bajarilish vaqtiga ega bo'lsa, u samarali deb ataladi.
Lekin, polinomial vaqt d ning katta qiymatlarida yaxshi natija bermasligi mumkin, masalan d>=100 holatda bu son juda katta bo’ladi, natijada polinomial bajarilish vaqti kattalashib ketadi. Algoritm ishlayveradi. Bu xolda N^d faqat chegara vazifasini o’taydi.