#pragma argsused #include #pragma hdrstop #include

Ω bahoni quyidagicha aniqlas mumkin Ω(g(n)) = {f (n): c va n₀ musbat o’zgarmaslar mavjudki , n₀ dan katta barcha n uchun  0 ≤ cg (n) ≤ f(n) munosabat o’rinli }. g(n) –bu  f(n) uchun aniq quyi asimptotik chegara . Bizning maqsadimiz berilgan algoritm tezligidan kam yoki teng bo'lgan eng yuqori o'sish g (n) ni olishdir .

Ω tahlilga misollar . 

Misol-1.

 f ( n ) = 5n²  uchun quyi chegarani toping .

Yechish : ∃ c, n₀  shunday: 0 ≤ cn² ≤ 5n²  ⇒ cn² ≤ 5n² ⇒ c = 5 va n₀ = 1

 ∴ 5n² = Ω ( n²)  c = 5 va n₀ = 1 .

2-misol.

 f ( n ) = 100n + 5 ≠ Ω(n²) ekanligini isbotlang .

Echish: shunday c ba n₀  uchun 0 ≤ cn² ≤ 100 n + 5

 100 n +5≤100 n +5 n  ( ∀ n≥ 1)=105n

cn² ≤105 n ⇒ n ( cn - 105)≤ 0 

n musbat bo'lganligi sababli ⇒ cn - 105≤0 ⇒ n≤ 105/ c  ⇒ Qarama-qarshilik: n o’zgarmasdan kichik bo'la olmaydi.

Tetta Θ baho ( o'rtacha asimptotik funktsiya) .

Ushbu bah0 berilgan funktsiyani (algoritm) yuqori va quyi chegaralari bir xilmi yo’ki bir hil emasligini aniqlaydi . Algoritmning o'rtacha ishlash vaqti har doim quyi va yuqori chegaralar orasida bo'ladi.

Agar yuqori chegara (O) va pastki chegara (Ω) bir xil natija beradigan bo'lsa , u holda Θ yozuvi ham bir xil o'sish tezligiga ega bo'ladi.

Masalan, f (n) = 10n + n  deb taxmin qilaylik. U holda uning aniq yuqori chegarasi g(n) - bu O(n) dir. O'sish darajasi eng yaxshisi g (n) = O (n) ga teng bo’lganda.

Ushbu misolda o'sish sur'atlari eng yaxshi va yomon holarlarda bir xil. Natijada , o'rtacha o’sish sur’ati ham bir xil bo'ladi.

Agar berilgan funktsiya (algoritm) uchun, O baho va Ω baholar mos kelmasa, u holda o'rtacha o'sish sur’ati ham mos kelmasligi mumkin. Bunday holda, biz barcha mumkin bo'lgan vaqt baholarini ko'rib chiqishimiz va ularning o'rtacha qiymatini olishimiz kerak .

Endi Θ bahoining ta'rifini ko'rib chiqamiz.

U quyidagicha aniqlanadi Θ(g (n)) = {f (n): shunday musbat c₁ , c₂ va n₀ o’zgarmaslar mavjudki 0 ≤ c₁ g (n) ≤ f (n) ≤ c₂ g(n) barcha n≥n₀ uchun munosabat o’rinli}. g(n)-bu f(n) uchun aniq asimptotik baho. Θ(g(n)) - g (n) bilan bir xil o'sish tartibidagi funktsiyalar to'plami.

1-misol : f (n) = n² /2-n / 2 uchun Θ-bahoni toping.

Echish: n² / 5≤ n² /2-n / 2 ≤ n² , barcha n≥2 uchun, 

bundan f (n) = Θ (n² ) => c₁ = 1/5, c₂ = 1 va n₀ = 2.

Misol 2 : n≠ Θ(n²) ni isbotlang. 

 c₁ n²  ≤ n ≤ c₂ n²  munosabat o’rinli faqat  n ≤ 1/c₁ bo’lsa, lekin n o’zgarmasdan kichik bo’lishi  mumkin emas, shuning uchun n≠ Θ(n²) bo'ladi..

Rasmda baholarni grafik tasviri ko'rsatilgan:

Bu baholardan boshqa o(g(n)) baho mavjud bo’lib, u quyidagi ko’rinishda aniqlanadi:

o(g(n))={f(n): har qanday o’zgarmas c uchun, shunday musbat n₀ mavjudki, 0 ≤ f (n) ≤ cg(n) tengsizlik barcha n > n₀ uchun o’rinli}. g (n) -bu f (n) uchun aniq yuqori asimptotik baho.

Tahlil qilish uchun (eng yaxshi holat, eng yomon holat va o'rtacha qiymat) biz yuqori chegarani (O) va quyi chegarani (Ω) va o'rtacha ish vaqtini (Θ) berishga harakat qilamiz. Ba'zan berilgan funktsiya (algoritm) uchun yuqori chegarani (O), quyi chegarani (Ω) va o'rtacha ish vaqtini (Θ) har doim ham olish mumkin bo’lmayda.

Agar biz algoritm uchun eng yaxshi variantni muhokama qilsak, biz yuqori chegarani (O) va quyi chegarani (Ω) va o'rtacha ish vaqtini (Θ) berishga harakat qilamiz.

Keyinchalik, biz odatda yuqori chegaraga (O) e'tibor qaratamiz, chunki algoritmning pastki chegarasi (Ω) amaliy ahamiyatga ega emas va biz uni yuqori va pastki chegaralar bir xil bo'lgan hollarda foydalanamiz . 

Yuqoridagi munozaradan anglash mumkinki, har bir holda berilgan f(n) funktsiya uchun boshqa g(n) funktsiya, qaysiki  n ning yuqori qiymatlarida f(n) ga yaqinlashadigan  g(n) funktsiyani topishga harakat qilmoqdamiz . Bu shuni anglatadiki g(n) ham egri chiziq bo’lib, yuqori qiymatlarida f(n) yaqinlashadi.

Matematikada biz bunday egri chiziqni asimptotik egri chiziq deb ataymiz. Boshqacha qilib aytganda, f(n) uchun g(n) asimptotik egri bo’ladi. Shu sababli algoritmlarni tahlilini asimptotik tahlil deymiz.