Mavzu: Asimptotik analizga murojaat usullari. Mummolar & yechimlar

2- ta’rif. f(n) funksiya Ω(g(n)) deyiladi, agar shunday musbat c va N lar mavjud bo’lsaki , barcha n>=N lar uchun f(n)>=cg(n) tengsizlik o’rinli bo’lsa.

Bu ta’rif ham birinchi ta’rifga juda o’xshash, faqat bu yerda tengsizlik teskaridir.

Yuqoridagi ikkita ta’rifdan foydalanib quyidagio ta’rifni keltirish mumkin.

Ta’rifga asosan f(n) funksiya kamida g(n) funksiya kabi o’sadi. Bu ikkita ta’rif yordamida funksiyalar o’rtasida quyidagi munosabatlar o’rinli bo’lishini aniqlash mumkin:

• 
  Ta’rifga asosan f(n) funksiya kamida g(n) funksiya kabi o’sadi. Bu ikkita ta’rif yordamida funksiyalar o’rtasida quyidagi munosabatlar o’rinli bo’lishini aniqlash mumkin:
  
• 
  3-ta’rif. f(n) funksiya Θ(g(n)) deyiladi, agar shunday musbat c1, c2 va N sonlar mavjud bo’lsaki, ular uchun barcha n>=N larda quyidagi tengsizlik o’rinli bo’lsa: c1*g(n)<=f(n)<=c*2g(n).
  

Misollar

• 
  Endi biz bir nechta misollarda assiptotik funcsiyalarni aniqlashni ko’rib chiqamiz.
  
• 
  Sodda sikl yordamida massiv elementlari yig’indisini hisoblashdan boshlaymiz. for (i = sum = 0; i < n; i++) sum += a[i]; Avval 2 ta o’zgaruvchini inisializatsiya qilamiz, sikl n ta iteratsiyadan iborat bo’lib, har bir qadamda yig’indi qiymati sum va i ni qiymati yangilanadi. Demak, algoritm vazifani to’liq yechish uchun 2+2n marta amallar bajarishi kerak bo’ladi, ya’ni bu holda assimptotik funksiya O(n) bo’ladi.
  

Agar ichma-ich joylashgan sikllar bo’lsa assimptotik funksiya darajasi ham ortib boradi. Buni quyidagi barcha nul holatdan boshlanuvchi massiv ostilarini yig’indisini hisoblash misolida ko’rish mumkin. Uning kodi: for (i = 0; i < n; i++) { for (j = 1, sum = a[0]; j <= i; j++) sum += a[j]; cout<<< i <<Sikl i ni initsializatsiya qilishdan boshlanadi, demak tashqi sikl n marta ishlaydi, va har bir ishlaganda ichki sikldagi 2 ta amal i marta, 3ta amal n marta takroran bajariladi. U holda bajarilgan amallar soni 1+3n + ∑2i=1+3n+n(n-1)=O(n)+ O(n^2) = O(n^2) kabi bo’ladi. Demak, masalani hal qilish uchun O(n^2) tartibdagi sonda amallar bajarilishi kerak.

• 
  Agar ichma-ich joylashgan sikllar bo’lsa assimptotik funksiya darajasi ham ortib boradi. Buni quyidagi barcha nul holatdan boshlanuvchi massiv ostilarini yig’indisini hisoblash misolida ko’rish mumkin. Uning kodi: for (i = 0; i < n; i++) { for (j = 1, sum = a[0]; j <= i; j++) sum += a[j]; cout<<< i <<Sikl i ni initsializatsiya qilishdan boshlanadi, demak tashqi sikl n marta ishlaydi, va har bir ishlaganda ichki sikldagi 2 ta amal i marta, 3ta amal n marta takroran bajariladi. U holda bajarilgan amallar soni 1+3n + ∑2i=1+3n+n(n-1)=O(n)+ O(n^2) = O(n^2) kabi bo’ladi. Demak, masalani hal qilish uchun O(n^2) tartibdagi sonda amallar bajarilishi kerak.