#pragma argsused #include #pragma hdrstop #include

Asimptotik baholar(taxminlar)

Eng yaxshi, o'rtacha va yomon holatlar uchun ifodalarga ega bo'lganimiz sababli, uchala holat uchun ham murakkablikning yuqori va pastki baholarini aniqlashimiz kerak . Ushbu yuqori va pastki chegaralarni ifodalash uchun bizga ba’zi belgilanishlar kerak .

Aytaylik, ushbu algoritmning murakkabligi f(n) funktsiya sifatida ifodalangan .

O - yuqori baho [yuqori chegara funktsiyasi]

Ushbu baho berilgan funktsiya uchun aniq yuqori chegarani beradi. Ular odatda f(n) = O(g(n)) shaklida yoziladi. Bu n ning katta qiymatlari uchun f(n) yuqori chegara  g(n) ga tengligini anglatadi.

 О baho  𝑓(𝑛) funktsiyasi  qandaydur n>n₀ dan boshlab g(𝑛) funktsiyasidan  osmasligini talab qiladi.

Misol uchun, agar f(n)=n⁴ +100n² +10n+50 algoritmning berilgan murakkabligi bo'lsa , u holda n⁴  bu g(n). Bu shuni anglatadiki, g(n) n ning katta qiymatlarida maksimal o'sish f (n) ni beradi.