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

Algoritmlarni eng yomon va o’rtacha holatlarda baholash
Bitta masalani hal qilish uchun turli xil algoritmlarni ko'rib chiqsak, ular
qancha hisoblash resurslarini (ishlash vaqti, xotira) talab qilishini tahlil
qilish va eng samaralisini tanlash foydalidir. Albatta, biz hisoblashning
qaysi
turidan
foydalanilganligi
to'g'risida
kelishib
olishimiz
kerak .. Algoritmning ishlash vaqti bilan biz bajaradigan elementar
qadamlar sonini tushunamiz.
Aytaylik
, psevdokodning bir qatorida
belgilangan miqdordagi operatsiyalar talab qilinadi (masalan, ba'zi
murakkab harakatlarning og'zaki tavsifi bo'lmasa - masalan, "hamma
nuqtalarni x-koordinata bo'yicha saralash"). Qo'ng'iroq qilish (qo'ng'iroq
qilish) protsedurasini (ma'lum miqdordagi operatsiyalarni oladi) va uning
bajarilishini (bajarilishini) farqlashingiz kerak, ular uzoq davom etishi
mumkin.
Algoritmning murakkabligi bu vazifaning o'lchamiga qarab talab
qilinadigan manbaning kattaligi tartibini (vaqt yoki qo'shimcha xotira)
aks ettiradigan qiymatdir.
Shunday qilib, biz algoritmning vaqtinchalik T (n) va fazoviy V (n)
murakkabligini ajratamiz. Murakkablikni baholashni ko'rib chiqishda biz
vaqtinchalik murakkablikdan foydalanamiz. Fazoviy murakkablik ham
shunga o'xshash tarzda baholanadi. Baholashning eng oson
usuli bu

---

eksperimental usul
, ya'ni algoritmni dasturlash va natijada olingan dasturni bir
nechta vazifalar bo'yicha bajarish, dasturlarning bajarilish vaqtini
baholash.
Biroq,
bu
usul
bir
qator
kamchiliklarga
ega.
Birinchidan,
eksperimental dasturlash
, ehtimol qimmat jarayon. Ikkinchidan,
shuni yodda tutish kerakki, dasturlarning bajarilish vaqtiga quyidagi
omillar ta'sir qiladi:
. Dastur algoritmining
vaqt murakkabligi
;
2. bajariladigan dasturning kompilyatsiya qilingan kodining sifati;
3. Dasturni bajarish uchun ishlatiladigan mashina ko'rsatmalari.
Ikkinchi va uchinchi omillarning mavjudligi algoritmning vaqt
murakkabligini o'lchashning tipik birliklaridan foydalanishga imkon
bermaydi (soniya, millisekundlar va boshqalar), chunki agar siz turli xil
dasturchilar (har bir algoritmni kim dasturlasa) bir xil algoritm uchun har
xil baholarni olish mumkin. o'z), turli xil kompilyatorlar va turli xil
kompyuterlar.
Ko'pincha, algoritmning vaqt murakkabligi kiritish hajmiga bog'liq.
Odatda algoritmning vaqt murakkabligi n o'lchamidagi kirish
ma'lumotlarini T (n) tartibiga to'g'ri keladi, deyiladi. Amaliyotda T (n)
ning aniq qiymatini aniqlash juda qiyin. Shuning uchun
ular
O-simvolizmidan foydalanib
, asimptotik munosabatlarga murojaat
qilishadi.
Keyinchalik muhokama qilinadigan algoritmning bajarilish vaqtini
nazariy jihatdan hisoblaydigan usul mavjud.

---