Oliy ta’lim,fan va innovatsiyalar vazirligi toshkеnt axborot tеxnologiyalari univеrsitеti “Algoritmlarni loyihalash

2. Algoritmlarni murakkabligini aniqlash

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:
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!
Demak,biz xulosa qilib, 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.