Laboratoriya ishi №1. Ma’lumotlarni saralash algoritmlarining murakkabligini tahlil qilish. Ustuvor navbatlar

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:

1. 
   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)

2. 
   O(f*g) = O(f)*O(g) – ikkita funksiya ko’paytmasining murakkabligini baholash ularning murakkabliklari ko’paytmasiga teng, masalan: