Mustaqil ish mavzu: Algoritmlarni vaqt bo’yicha va hajmiy murakkabligini baholash uchun tekis va logarifmik baholash usullari. Bajardi: Pardayev Jonibek Tekshirdi: Narmanov Otabek

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: