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

Algoritmlarni murakkabligini aniqlash -
Algoritmlarni tahlil
qilishning asosiy vazifasi kirish ma'lumotlari hajmining oshib
borishi bilan resurslarga bo'lgan talabni (vaqt va xotira xarajatlari)
o'lchash usullarini aniqlashdir. Shundan so'ng, o'sish sur'ati
qonuniyatlarini tavsiflash uchun zarur bo'lgan matematik mexanizm
ishlab chiqiladi. Kirish ma'lumotlari hajmini oshirish bilan turli xil
funktsiyalar; "bitta funktsiya boshqasiga qaraganda tezroq o'sadi"
iborasi nimani anglatishini aniqlab olishga yordam beradi.
Ba'zi hollarda, yaxshi bajarilish vaqtiga erishish yanada murakkab
ma'lumotlar tuzilmalaridan foydalanishga bog'liq va bo'lim oxirida
biz bunday ma'lumotlar strukturasining juda foydali misolini ko'rib
chiqamiz: ustuvor navbatlar va ularni uyum(kucha, heap) asosida
amalga oshirish.
Asosiy maqsad - hisoblash muammolarining samarali algoritmlarini
izlash. Ushbu umumiylik darajasida kompyuterni hisoblashning
butun sohasi ushbu mavzu bilan bog'liq bo'lib tuyuladi; bizning
yondashuvimiz boshqalardan qanday farq qiladi? Algoritmlarni
ishlab chiqishda umumiy mavzular va loyihalash tamoyillarini
aniqlashga harakat qilamiz. Bizni samarali algoritmlarni
loyihalashning asosiy usullarini minimal ma'lumot bilan namoyish
etuvchi paradigmatik masalalar va usullar qiziqtiradi.
Algoritmni bajarilish qadami - bu ijrochi tomonidan bitta
ko‘rsatmaning bajarilishidir. Bir masalani hal etuvchi
ikkita 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
AKRORLANSIN 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):