Samarqand davlat universiteti raqamli texnologiyalar fakulteti

Asimptotik baholashning ko’rinishlari

F(n)> 0 murakkabligini, bir xil tartibdagi g(n)> 0 funksiyasini, kirish n>0 o'lchamini ko'rib chiqaylik.

Agar f(n) = O (g(n)) va n> n₀ uchun c>0, n₀> 0 konstantalar mavjud bo'lsa, u holda 0
Bu holda g(n) funksiyasi f(n) uchun asimptotik-aniq baho hisoblanadi. Agar f(n) algoritmning murakkablik funksiyasi bo'lsa, unda murakkablik tartibi f(n) uchun - O(g(n)) deb belgilanadi.

Ushbu ibora doimiy koeffitsiyentgacha g(n) dan tez o'smaydigan funksiyalar sinfini belgilaydi.

Asimptotik funksiyalarga misollar

f(n)	g(n)
8	1