Algoritmlarning samaradorligi va ularning tahlili

1-ta’rif. f(n) funksiya 0(g(n)) bo’ladi deyiladi, agar shunday musbat c va N sonlar mavjud bo’lsaki , barcha n>=N lar uchun f(n)<=c g(n) tengsizlik bajarilsa.

Bu ta’rifga asosan agar f(n) funksiya 0(g(n)) bo’lsa, u holda uning o’sish tartibi yetarli katta n lar uchun albatta cg(n) funksiya o’sish tartibidan kichik yoki teng bo’lar ekan. Demak, bu holda f(n) funksiya katta n larda cg(n) funksiyadan tez o’sa olmaydi. Bu yerda c va N sonlarini aniqlash muammo bo’lib qoladi, chunki ta’rifda ularni aniqlashning konkret yoli korsatilmagan. Ikkinchidan, bu sonlarga hech qanday shartlar qo’yilmagan. Shuning uchun ularning qiymatlari juda ko’p bo’lishi mumkin. Masalan,

f(n)=2n²+ 3n+1=O(n²) (2)

U holda g(n)=n² funksiyani tarifdagi funksiya sifatida oluvchi funksiyalardan biri deb xisoblash mumkin. Ta’rifga asosan, c va N lar uchun quyidagi rasmdagi sonlar juftliklarini olish mumkin bo’ladi:

2-rasm. (2) funksiya uchun c va N larning qiymatlari.

N va c ning bunday qiymatlarini quyidagi tengsizlikni yechish orqali aniqlanadi:

2n²+3n+1<=cn²; (3)

Bu tengsizlikdan ko’rinib turibdiiki, 2 ta o’zgaruvchi 1 ta tengsizlikni qanoatlantirilishi kerak, demak ulardan 1 tasini erkli tanlasak , unga bog’liq ravishda ikkinchisini (3) tengsizlikni yechib aniqlaymiz yoki buni teskarisini ham qilish mumkin . Undan tashqari n ning darajalari bo’yicha ham assimptotik funksiyalarni juda ko’pini olish mumkin.

3-rasm. 2-rasmdagi N ning har hil qiymatlari uchun

funksiyalarni solishtirish.

Bu holda eng kichik tartiblisi tanlab olinadi. Bunday noaniqliklarni xal qilish berilgan funksiyadagi kichik tartibli xadlarni barchasini tashlab yuborish va quyidagicha belgilash orqali amalga oshiriladi. Masalan, (1) funksiya uchun

f(n)=n²+100n+O(log₁₀n)

ko’rinishda olish , (2) funksiya uchun esa f(n)=2n²+O(n) kabi ko’rinishda olish mumkin bo’ladi.

Endi O- katta funksiyalarning quyiodagi xossalarini isbotsiz keltirib o’tamiz.

1. 
   Tranzitivlik. Agar f(n) funksiya O(h(n)) bo’lsa, u holda f(n) funksiya O(h(n)) bo’ladi.
   
2. 
   Agar f(n) va g(n) funksiyalarning xar biri O(h(n)) bo’lsa, u holda ularning yig’infisi f(n)+g(n) ham O(h(n)) bo’ladi.
   
3. 
   f=an^k funksiya O(n^k) bo’ladi.
   
4. 
   f=n^k funksiya ixtiyoriy j>=0 uchun O(n^k+j) bo’ladi.
   

Yuqoridagi hossalardan

f(n)=a_kn^k+ a_k-1n^k-1+…+ a₁n+ a₀

funksiyaning O(n^k) bo’lishi kelib chiqadi.

Algoritmlar samaradorligini baxolashda eng muhim funksiyalardan biri bu logarifmik funksiya hisoblanadi. Xaqiqatdan ham, tartibi logarifmik funksiya kabi bo’lgan algoritm juda yaxshi hisoblanadi, chunki undagi amallar soni nisbatan juda kam bo’ladi. Logarfmik funksiya bilan bog’liq hossani keltirishdan avval yana bir muhim faktni keltiramiz.

5. 
   Agar f(n)=Cg(n) bo’lsa, u holda f(n) funksiya O(g(n)) bo’ladi.
   
6. 
   Ihtiyoriy a=emas 1, b=emas 1 sonlar uchun log_an funksiya O(log_bn) bo’ladi.