Tayanch so’zlar

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.