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

algoritmdan 
kam qadam talab qilinayotgani samaraliroqdir. 
Samaradorlik 
o‘lchovi - 
bu bor-yo‘g‘i qadamlar sonidir. Lekin chuqurroq e’tibor berib qarasak, bu 
ta’rifdagi 
mujmal 
tomonlarni aniqlaymiz. Ba’zan avval uchragan 
algoritmlardagidan 
ko‘ra vaziyat murakkabroq 
bo’ladi. 

---

Algoritmlar 
murakkabligi 
bilan 
ham 
farqlanishi 
mumkin. 
Algoritmning murakkabligini uning matnidagi satrlar soni bilan 
o‘lchaymiz. Shu bilan birga quyidagi ikki satrni bir 
tuzilmaning 
ikki 
qismi bo‘lgani uchun bittaga hisoblaymiz 
TAKRORLANSIN MARTA TAMOM
Mana, masalan, quyidagi algoritmda:
1 ni qo‘sh
TAKRORLANSIN 6 MARTA 2 ga ko‘paytir
1 ni qo‘sh
TAMOM
1 ni qo‘sh
TAKRORLANSIN 6 MARTA
TAMOM
2 ga ko‘paytir
1 ni qo‘sh
faqat 4 ta satr 
bor. Bu uning murakkabligi 4 ekanligini bildiradi.
Shuni aytib o‘tish joizki, hozir biz ko’rgan algoritm murakkabligi va 
samaradorligi o‘zaro tengdir. Masalan, bo‘ri, echki va karamni daryodan 
o‘tkazish algoritmi ham 7 satrdan iborat ham u 7 qadamda bajariladi.
Bu yerda bizni kerakli vositamiz bor: bu TAKRORLANSIN - 
MARTA tuzilmasi. Shuning uchun oshiruvchi tomonidan 17 sonini hosil 
qilish algoritmi 3 satrdan iborat bo‘ladi (eslatma: tuzilma 1 ta satr deb 
hisoblanadi):
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: