#pragma argsused #include #pragma hdrstop #include

O (n²) o’z ichiga O(1), O (n), O ( nlogn ) va boshqalarni oladi .

Algoritmlarni faqat n ning katta qiymatlari uchun tahlil qilish kerak. Bu shuni anglatadiki, n₀ dan kichiklarini ko’rmasak ham bo’ladi.

Misollar:

Misol-1. f (n) = 3n + 8 uchun yuqori chegarani toping.

Yechish: 3n + 8 ≤ 4n hamma n ≥ 8 uchun.

 ∴ 3n + 8 = O (n), c = 4 va n₀ = 8.

Misol-2. f (n) = n² + 1 uchun yuqori chegarani toping.

Yechish: n²  + 1≤ 2n² hamma n≥1 uchun.

∴ n² + 1 = O (n² ), c = 2 va n₀ = 1.

Misol-3 f (n) = n⁴ + 100n² + 50 uchun yuqori chegarani toping.

Yechish: n⁴ + 100n² + 50 ≤ 2n⁴ barcha n ≥ 11 uchun.

 ∴ n⁴ + 100n² + 50 = O (n⁴) , c = 2 va n₀ = 11.

Yagona emasmi?

Asimptotik bahoni isbotlashda n₀ va c uchun yagona qiymatlar to'plami mavjud bo’lmasligi mumkin.

100n + 5 = O(n) ni ko'rib chiqamiz.

 Ushbu funktsiya uchun n₀ va c ning bir nechta qiymatlari mavjud .

Yechim1: 100n + 5≤ 100n + n = 101n≤ 101n, barcha n≥5ucun tengsizlik o’rinli, n₀ = 5 va c = 101  echim bo’ladi.

Yechim 2: 100n + 5≤100n + 5n = 105n≤105n, barcha n> 1 uchun tengsizlik o’rinli, n₀ = 1 va c = 105 ham yechim bo’ladi.

 Omega baholash –Ω[pastki chegara funktsiyasi]

 O ning muhokamasiga o'xshab, bu baho berilgan algoritm uchun aniqroq pastki chegarani beradi va f (n) = Ω(g(n)) deb yoziladi. Bu shuni anglatadiki, n ning katta qiymatlar uchun g (n) funktsiya f (n) uchun pastki chegara hisoblanadi.

Misol uchun, agar f (n) = 100n²  + 10n + 50 bo’lsa, g (n) - bu Ω (n² ) dir.