Texnologiyalari universiteti mustaqil ish

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.