6
Biz odatda
n ning kichik qiymatlarini rad etamiz. Bu shuni anglatadiki,
n ning
kichik qiymatlarida o'sish tezligi unchalik muhim emas.
Ifodadagi n
0
nuqta altoritmning ushbu nuqtadan boshlab o'sish tezligini
qarashimiz kerak bo'lgan nuqta. O’sish tezligi n
0
dan kichik bo'lganda boshqacha
bo'lishi mumkin. n
0
– ushbu funksiyaning chegarasi deyiladi.
O(g(n)) - oʻsish tartibi g(n) dan kichik yoki bir xil boʻlgan funksiyalar toʻplami.
Masalan:
O(n
2
) tarkibiga O(1), O(n), O(nlogn) va boshqalar kiradi.
Algoritmlarni faqat
n ning katta qiymatlari uchun tahlil qilish kerak. Bu shuni
anglatadiki, n
0
dan kichik bo’lgan xollarni hisobga olmasligimiz mumkin.
Big-O uchun misollar:
1-misol. f(n) = 3n + 8 uchun yuqori chegarani toping
Yechish: hamma n ≥ 8 uchun 3n + 8 ≤ 4n
∴ 3n + 8 = O(n) bo’lib, c = 4 va n
0
= 8 ga teng bo’ladi;
2-misol. f(n) = n
2
+ 1 uchun yuqori chegarani toping
Yechish: hamma n ≥ 1
uchun n
2
+ 1 ≤ 2n
2
∴ n
2
+ 1 = O (n
2
) bo’lib, c = 2 va n
0
= 1 ga teng bo’ladi;
3-misol. f(n) = n
4
+ 100n
2
+ 50 uchun yuqori chegarani toping.
Yechish: hamma n ≥ 11 uchun n
4
+ 100n
2
+ 50 ≤ 2n
4
∴ n
4
+ 100n
2
+ 50 = O(n
4
) bo’lib, c = 2 va n
0
= 11 teng bo’ladi.
O'ziga xoslik yo'qmi?
Asimptotik baholarni isbotlashda n
0
va c uchun yagona qiymatlar to'plami
mavjud emas.
Masalan, 100n + 5 = O(n) ifodani ko’rib chiqaylik.
Bu funksiya uchun n
0
va c ning bir nechta qiymatlari mavjud.
1-yechim: 100n + 5 ≤ 100n + n = 101n ≤ 101n, bu xolda barcha n ≥ 5 uchun n
0
= 5 va c = 101 bo’lgan qiymatlar yechim hisoblanadi.
2-yechim: 100n + 5 ≤ 100n + 5n = 105n ≤ 105n, bu xolda barcha n > 1 uchun n
0
= 1 va c = 105 bo’lgan qiymatlar yechim hisoblanadi.
