O’zbekiston respublikasi axborot texnologiyalai va kommunikatsiyalarini rivojlantirish vazirligi muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti qarshi filiali

Mazmuni
Tavsifi
f(n) ∈ Ο(g(n))	f yuqoridan g funksiya bilan doimiy ko'paytiruvchi aniqligigacha chegaralangan
f(n) ∈ Ω(g(n))	f quyidan g funksiya bilan doimiy ko'paytiruvchi aniqligigacha chegaralangan
f(n) ∈ Θ(g(n))	f yuqori va quyidan g funksiya bilan chegaralangan

Misol uchun, muassasaning tozalash vaqti uning maydoni kattaligiga chiziqli ravishta bog’liq (Θ(S)), ya’ni maydon kattaligining n marta ortishi bilan uni tozalash vaqti ham n marta ortadi. Telefon daftarchasidan ismni qidirishda agar chiziqli qidirish algoritmidan foydalanilsa, O(n) chiziqli vaqtni talab etadi. Agar ikkilik qidiruvdan foydalanilsa, u holda (Ο(log₂(n))) yozuvlar soniga logarifmik bog’liq bo’ladi.
Biz O – funksiya bilan ko’proq kuzatuvlar olib boramiz. Keyingi kuzatishlarda algoritmlarning murakkabligi yuqori asimptotik chegara bilan beriladi.
Asimptotik tahlilning muhim qoidalari:
O(k*f) = O(f) – doimiy ko’payuvchi k (konstanta) tashlab yuboriladi, chunki doimiy kirish ma’lumotlarining ortishi bilan uning ahamiyati yo’qoladi, masalan:
O(9,1n) = O(n)
O(f*g) = O(f)*O(g) – ikkita funksiya ko’paytmasining murakkabligini baholash ularning murakkabliklari ko’paytmasiga teng, masalan:
O(5n*n) = O(5n)*O(n) = O(n)*O(n) = O(n*n) = O(n²)
O(f/g)=O(f)/O(g) – ikkita funksiyaning bo’linmasining murakkabligi ular murakkabliklarining bo’linmasiga teng, masalan: