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



Download 30,55 Kb.
bet2/8
Sana31.01.2021
Hajmi30,55 Kb.
#58040
1   2   3   4   5   6   7   8
Bog'liq
Laboratoriya 1 - AL
Laboratoriya 1 - AL, УЗЕЛ СВЯЗИ Министерство обороны Российской Федерации, УЗЕЛ СВЯЗИ Министерство обороны Российской Федерации, topshiriq 8(2), O‘zbekistonda va chet mamlakatlarda elementar matematik tasavvurlarni shakllantirish metodikasi asoslarining rivojlanishi, 1-topshiriq, 16366062544245126 (1), 16366062544245126 (1), 16366062544245126, 16366062544245126, 16366062544245126, Лойиҳа матни - 201638-(212079), Лойиҳа матни - 201638-(212079), Fotoeffekt hodisasining amaliyotda qo\'llanilishi Shamsiboyev Javlonbek
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 (Ο(log2(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)

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


Download 30,55 Kb.

Do'stlaringiz bilan baham:
1   2   3   4   5   6   7   8




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2022
ma'muriyatiga murojaat qiling

    Bosh sahifa
davlat universiteti
ta’lim vazirligi
maxsus ta’lim
zbekiston respublikasi
axborot texnologiyalari
O’zbekiston respublikasi
guruh talabasi
nomidagi toshkent
o’rta maxsus
davlat pedagogika
texnologiyalari universiteti
toshkent axborot
xorazmiy nomidagi
Ўзбекистон республикаси
rivojlantirish vazirligi
pedagogika instituti
таълим вазирлиги
махсус таълим
haqida tushuncha
O'zbekiston respublikasi
tashkil etish
toshkent davlat
vazirligi muhammad
saqlash vazirligi
kommunikatsiyalarini rivojlantirish
respublikasi axborot
vazirligi toshkent
bilan ishlash
Toshkent davlat
uzbekistan coronavirus
sog'liqni saqlash
respublikasi sog'liqni
koronavirus covid
coronavirus covid
vazirligi koronavirus
risida sertifikat
qarshi emlanganlik
sertifikat ministry
covid vaccination
vaccination certificate
Ishdan maqsad
o’rta ta’lim
fanidan tayyorlagan
matematika fakulteti
haqida umumiy
fanidan mustaqil
moliya instituti
fanining predmeti
pedagogika universiteti
fanlar fakulteti
ta’limi vazirligi