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

Algoritmlarni vaqt va hajmiy murakkablik bo’yicha baholashda tekis va
logarifmik solishtirma mezonlar
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
4.Taqribiy integrallash usuli va aniqligi bo’yicha hisoblash
Oliy matematika kursidan malumki aniq integrallar asosan
N‘yuton-Leybnits formulasi bilan hisoblanadi. Yani quyidagi formula
bilan hisoblanadi:
Bu
yerda