Mavzu: Asimptotik analizga murojaat usullari. Mummolar & yechimlar

Agar n o’lchov va t vaqt orasida t1=c*n chiziqli bog’liqlik bo’lsa, u holda xajmni bir necha marta, hususan 5 marta, oshirish natijasida, ularni qayta ishlashga ketgan vaqt ham 5 marta oshadi ya’ni n2=5*n bo’lsa, t2=5*t o’rinli bo’ladi. Yoki, agar bog’liqlik t1=logn bo’lsa, u holda n 2 marta oshirilsa vaqt sarfi bor yo’g’i bir birlikka ortadi, ya’ni t2=log2*n=t1+1 bo’ladi. n va t ni bog’liqligini ifodalovchi funksiya odatda murakkab bo’ladi va bunday funksiyani hisoblash katta hajmdagi ma’lumotlarni qayta ishlashda juda muhim hisoblanadi. Hosil qilingan f-ya berilgan funksiyaning tarkibiy samaradorligini bildiradi.Shunga qaramay bu yaqinlashish funksiyaga yaqin hisoblanadi, va katta hajmdagi ma’lumotlar uchun originalga juda yaqin bo’ladi. Samaradorlikning bu o’lchovi assimtotik yaqinlashuvchi o’lchov deyiladi va u samaradorlikni aniqlovchi funksiya ma’lum xadlarini hisobga olganda yoki samaradorlikni aniq hisoblas qiyin, yoki mumkin bo’lmaganda qo’llaniladi.

Quyidagi misolni ko’ramiz:

• 
  Quyidagi misolni ko’ramiz:
  
• 
  (1)
  
• 
  n ning kichik qiymatlarida ohirgi had 1000 ning funksiya qiymatini hosil bolishidagi ulushu qolganlariga nisbatan katta hisoblanadi. n=10 bo’lganda 2-xad 100n va ohirgi 1000 xadlar teng bo’ladi va boshqalarga nisbatan funksiya qiymatiga bir xil ta’sir ko’rsatadi. Bu xadlarni funksiya xar bir xadining uning qiymatiga qanday ta’sir qilishining miqyosi n ning har hil qiymatlari uchun quyidagi jadvalda keltirilgan.
  

Hadlarning funksiya qiymatiga ta’sir qilish miqyosi.

Бахолаш функциялар классификацияси.

Berilgan ikkita f va g funksiyalar uchun quyidagi ta’rifni keltiramiz:

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