Algoritmlarni baholash. (Big-O)

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
A2
A3
A4
A5

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		1000	60*100
A2		140	4893
A3		31	244	1897
A4		10	39	153
A5		9	15	21

“O-yozuv” usulning kamchiligi shundaki – konkret berilganlar uchun dastur bajarilishiga aniq sarflanayotgan vaqtni hisoblab bilmaymiz, faqatgina qadamlar bajarilish soni 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; icin>>a[i];
for(int i=0; i a[i]*=2;

Bu yerda sikl operatori (for(int i=0; i