Ish mavzu: Algoritmlarni vaqt va hajmiy murakkabligini baholashda tekis va logarifmik solishtirma mezonlari

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
.