Rivojlantirish vazirligi muhammad al-xorazmiy nomidagi

Algoritmlarni 
asimptotik 
(O()) 
baholash 
– algoritmda kiruvchi 
ma’lumotlarning bajariladigan amallar soniga ma’lum bir qonuniyatlar asosida 
mos qo’yilishidir. Bu qonuniyatlar kvadratik, factorial, logarifmik bo’lishi 
mumkin.
Agar kiruvchi ma'lumotlarning o'lchamlari oshsa, algoritmning bajarilish vaqti 
f(N) funksiyasi bilan bir xil tezlikda oshsa, algoritmda O(f(n)) murakkablik bor.
Agar kiruvchi ma'lumotlarning o'lchamlari oshsa, algoritmning bajarilish vaqti 
f(N) funksiyasi kvadratik tezlikda oshsa, algoritmda O(f(n^2)) murakkablik bor.
Uch asimptotik belgilar asosan algoritmlarning vaqt murakkabligini ifodalash uchun 
ishlatiladi :
1. Θ-notation ( teta );  
2. O-notation ( O );
3. Ω notasi ( Omega ).  
Hisoblash mashinalar tezligi oshishiga qaramasdan, ular yordamida 
yechilayotgan masalalar kattaligini oshishini algoritm qiyinligini tahlil orqali 
aniqlaydi.
Faraz qilaylik, A1,A2,…,A5  nomli 5 ta algoritm quyidagi vaqtli qiyinliklar 
bilan berilgan.
Algoritm
Vaqtli qiyinlik
A1
N
A2
Nlog
2
n

---

A3
N
2
A4
N
3
A5
2
n
Bu yerda vaqtli qiyinlik – bu n kattalikdagi kirishlarni qayta ishlash uchun 
kerak bo’ladigan vaqt birliklar soni. Masalan, vaqt birligini 1 millisekund deb qabul 
qilaylik.
Bunda A1 algoritm bir sekundda 1000 kattalikdagi kirishni qayta ishlash 
mumkin, A5 algoritmi esa kirish kattalikdagina 9 dan oshirib bilmaydi.
Keyingi jadval 1 sekundda, 1 minutda, 1 soatda 5 ta algoritmlarni har birining 
yordamida yechiladigan masalaning kattaligi keltirilgan.
Algoritm
Vaqtli qiyinlik
Masalaning maksimal o’lchami
1 sek
1 min
1 soat
A1
N
1000
60*100
3,6*10
6
A2
Nlog
2
n
140
4893
2*10
4
A3
N
2
31
244
1897
A4
N
3
10
39
153
A5
2
n
9
15
21

---

“O-yozuv” usulning kamchiligi shundaki – konkret berilganlar uchun dastur 
bajarilishiga aniq sarflanayotgan vaqtni hisoblab bilmaymiz, faqatgina qadamlar 
bajarilish soni 
O(n )
bo’lganini bildik. Lekin bu usul bilan tahlil qilish qulay, va 
berilgan amaliy masala uchun dasturni samaradorligini aniqlaydigan dastlabki 
hisoblashlar uchun algoritmning isahlash vaqtini assimptotik bahosini beradi.
Samaradorlikni baholashga misollar
Masala, Qalam va qog’oz yordamida, quyidagi 16 ta kvadratdan iborat shaklni
yasash kerak.
1 2
3
4
5 6
7
8
9 10 11 12
13 14 15 16
Algoritm bahosi O(n)

---

Bu jarayon 4 ta qadamda bajarildi. Demak algoritm bahosi O(logN)
Agar biz dasturimizda bir o’lchovli massivdan foydalansak, bu kamida O(n) bilan 
baholanadi.
Masala. Bir o’lchovli massivning elementlarini 2 ga ko’paytirish algoritmini 
baholang for(int i=0; i>a[i];
for(int i=0; ia[i]*=2;

---

Bu yerda sikl operatori (for(int i=0; iO(3n) deb baholashimiz mumkin. O(cn)=O(n). baholash bo’lganligi uchun bizning 
algoritmning bahosi ham O(n) ga teng.
Masala. Ikki o’lchovli massivning elementlarini 2 ga ko’paytirish algoritmni 
baholang.
for(int 
i=0; 
ii++)
for(int j=0; j{
a[i][j]*=2;
}
 Bu algoritmning matematik modeli
𝑛
𝑛 
𝑛
𝑆
𝑛
𝑖
𝑖 
𝑛 
𝑖 
𝑛
→𝑂
𝑑𝑒𝑚𝑎𝑘,𝑏𝑢 𝑎𝑙𝑔𝑜𝑟𝑖𝑡𝑚𝑛𝑖𝑛𝑔 𝑏𝑎ℎ𝑜𝑠𝑖 𝑂(𝑛
2
)

---