Ω – quyi bahosi [pastki chegara funktsiyasi]

Download 0.73 Mb. Pdf ko'rish
bet	5/6
Sana	22.11.2023
Hajmi	0.73 Mb.
	#103483

1 2 3 4 5 6

Bog'liq
Ma\'ruza 2. Algoritmlar tahlili
2023 YIL, file, 0GuNYUHUW0jsf44WOD6Nnc8WvkZQKMaQsh4xGi3V, 1-kurs kechki o\'zbek, 1 Axborot manbalari va axborotga bulgan extiyoj Axborot savodxon, 9-1 Маъруза№5, Kitob 5571 uzsmart.uz, Boltabayev M.P.Kichik biznes va tadbirkoplik, acmp.ru dan ro\'yxatdan o\'tish, Abdurahmonov jahongir, TSawyer, jamshid kur ishi gidralogiya1, Mustaqil ish, New Microsoft Word Document

Ω – quyi bahosi [pastki chegara funktsiyasi]
O – yuqori baho kabi, ushbu baho berilgan algoritm bo'yicha aniqroq pastki
chegarani beradi va f(n) = Ω(g(n)) shaklida yoziladi. Bu n ning yetarlicha katta
qiymatlari uchun g(n) funksiya f(n) ning pastki chegarasi ekanligini anglatadi.
Masalan, agar f(n) = 100n
2
+ 10n + 50 bo'lsa, g(n) – Ω (n
2
) ga teng.
Ω quyi bahoning matematik ta'rifini beraylik.
Ω(g(n)) = {f(n): ∃ c va n
0
musbat konstantalar mavjudki, barcha n > n
0
uchun 0
≤ cg(n) ≤ f(n) bo’ladi}. g(n) – f(n) uchun asimptotik aniq quyi chegara (baho) bo’ladi.
Bizning maqsadimiz berilgan algoritm tezligidan kichik yoki teng bo'lgan g(n) ning
eng yuqori o'sish tezligini olishdir.

7
Ω –quyi baholashga misollar:
1-misol. f(n) = 5n
2
uchun quyi chegarani toping.
Yechish:
∃ c, n
0
mavjudki: 0 ≤ cn
2
≤ 5n
2
⇒ cn
2
≤ 5n
2
⇒ c = 5 va n
0
=1
∴ 5n2 = Ω (n
2
) bo’lib, c = 5 va n
0
= 1 ga teng bo’ladi;
2-misol. f(n) = 100n + 5 ≠ Ω (n
2
) ekanligini isbotlang.
Yechish:
∃ c, n
0
mavjudki: 0 ≤ cn
2
≤ 100n + 5
100n + 5 ≤ 100n + 5n(
∀n ≥ 1) = 105n
cn
2
≤ 105n
⇒ n(cn - 105) ≤ 0
n musbat bo'lgani uchun
⇒cn - 105 ≤0 ⇒ n ≤105/c
⇒ Qarama-qarshilik: n konstantadan kichik bo'lishi mumkin emas.
Θ - o’rta baho (o'rtacha asimptotik funktsiya)
Bu baho berilgan funksiya (algoritm) ning yuqori va pastki chegaralari bir xil
yoki yo‘qligini aniqlaydi. Algoritmning o'rtacha ishlash vaqti har doim pastki va
yuqori chegaralar orasida bo'ladi.
Agar yuqori chegara (

Download 0.73 Mb.

1 2 3 4 5 6

Download 0.73 Mb.

Pdf ko'rish