O) va quyi chegara (
Ω)
bir xil natijani bersa, u holda Θ
ham bir xil o'sish tezligiga ega bo'ladi.
Misol tariqasida f(n) = 10n + n ifodani qaraylik.
U holda uning aniq yuqori chegarasi g(n) –
O(n) dir. Eng yaxshi o'sish tezligi
g(n) =
O(n).
Uning aniq quyi chegarasi g(n) –
Ω(n) dir. Eng yomon o'sish tezligi g(n) =
Ω(n).
Ushbu misolda eng yaxshi va eng yomon o'sish tezliklari bir xil. Natijada,
o'rtacha holat ham bir xil bo'ladi.
Berilgan funktsiya (algoritm) uchun, agar
O va
Ω baholar mos kelmasa, u holda
o'rtacha o'sish tezligi mos kelmasligi mumkin. Bunday holda, biz
barcha mumkin
bo'lgan vaqt baholarini qarab chiqishimiz va ularning o'rtacha qiymatini hisoblashimiz
kerak bo’ladi.
Endi
Θ –
o’rtacha baho ta'rifini beraylik.
Θ(g(n)) = {f(n): ∃
c
1
,c
2
va
n
0
musbat konstantalar mavjudki, barcha n > n
0
uchun 0
≤ c
1
g(n) ≤ f(n) ≤ c
2
g(n) bo’ladi}. g(n) – f(n) uchun asimptotik aniq chegara
(baho) bo’ladi.
Θ(g(n)) – g(n) kabi o’sish tartibga ega funksiyalar sinfini ifodalaydi.
Quyida
Θ – o’rtacha baho uchun misollarni ko’rib chiqamiz:
1-misol. f(n)=n
2
/2-n/2 uchun Θ -bahoni toping
Yechish: barcha n≥2 uchun n
2
/5≤ n
2
/2-n/2 ≤ n
2
, demak
f(n)= Θ(n
2
) bo’lib, c
1
=1/5, c
2
=1, n
0
=2 ga teng bo’ladi;
2-misol: n≠ Θ (n
2
)
ekanligini isbotlang
c
1
n
2
≤ n ≤ c
2
n
2
munosabati faqat n ≤ 1/c
1
uchun to‘g‘ri, lekin n konstantadan
kichik bo‘lishi mumkin emas, shuning uchun n ≠ Θ (n
2
)
8
Rasmda baholarning grafik ko'rinishi ko'rsatilgan:
Ushbu baholashlardan tashqara yana boshqa o(g(n)) baholash ham mavjud
bo'lib, u quyidagicha aniqlanadi:
o(g (n)) = {f (n): har qanday c konstanta uchun shunday musbat n
0
son mavjud
bo’lib, barcha n > n
0
uchun 0 ≤ f (n) ≤ cg (n) o’rinli bo’ladi}. U xolda g(n) – f (n)
uchun asimptotik aniq yuqori baho bo'ladi.
Tahlil qilish uchun (eng yaxshi, eng yomon va o'rtacha holat) biz
yuqori chegara
(O) va pastki chegara (Ω) va o'rtacha ishlash vaqtini (Θ) berishga harakat qilamiz.
Ba'zan berilgan funktsiya (algoritm) uchun yuqori chegara (O) va pastki chegara (Ω)
va o'rtacha ishlash vaqtini (Θ) olishning har doim ham imkoni bo’lmaydi.
Agar biz algoritmning eng yaxshi versiyasini muhokama qilsak, biz yuqori
chegara (O) va pastki chegara (Ω) va o'rtacha ishlash vaqtini (Θ) berishga
harakat
qilamiz.
Keyinchalik biz odatda yuqori chegaraga (O) e'tibor qaratamiz, chunki
algoritmning pastki chegarasi (Ω) amaliy ahamiyatga ega emas va biz undan yuqori va
pastki chegaralar mos bo'lgan hollarda foydalanamiz.
Yuqoridagi muhokamadan shuni ko'rish mumkinki, har
bir holatda, berilgan f(n)
funksiya uchun
n ning yetarlicha katta qiymatlarida yaqinlashadigan boshqa g(n)
funksiyani topishga harakat qilamiz. Demak, g(n) ham f(n) ga
n ning katta qiymatlarda
yaqinlashadigan egri chiziqdir.
Matematikada bunday egri chiziqni asimptotik egri chiziq deb ataymiz.
Boshqacha qilib aytganda, g(n) – f(n) uchun asimptotik egri chiziqdir. Shu sababga
ko’ra algoritmlarni tahlil qilishni asimptotik tahlil deb ataymiz.
Asimptotik baholarning asosiy xossalari
• Tranzitivlik: f(n) = Θ(g(n)) va g(n) = Θ(h(n)) ⇒ f(n) = Θ(h(n)). Bu O va Ω
baholar uchun ham amal qiladi.
• Refleksivlik: f(n) = Θ (f(n)). Bu O va Ω baholar uchun ham amal qiladi.
• Simmetriyalik: f(n) = Θ(g(n)) bo’ladi, agar g(n) = Θ(f(n)) bo‘lsa.
• Simmetriya transpozitsiyasi: f(n) = O(g(n)) agar g(n) = Ω (f(n)) bo'lsa.
