Mustaqil ish mavzu: Algoritmlarni vaqt bo’yicha va hajmiy murakkabligini baholash uchun tekis va logarifmik baholash usullari. Bajardi: Pardayev Jonibek Tekshirdi: Narmanov Otabek
Download 141.98 Kb. Pdf ko'rish
|
Pardayev Jonibek
- Bu sahifa navigatsiya:
- 1.1-rasm 1.2-rasm 1.3-rasm 1.4-rasm 1.5-rasm
|
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! 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. Download 141.98 Kb. Do'stlaringiz bilan baham: 
|