Algoritmlarning samaradorligi va ularning tahlili

Sigma(Ω) va Tetta(Θ) baholashlar.

O- notasiya yordamida funksiyani yuqoridan assimptotik baxolashni ko’rdik. Xuddi shunday baxolashni quyidan ham berish mumkin. Bunday baholashni sigma(Ω) baholash deyiladi va u quyidagicha aniqlanadi:

2- ta’rif. f(n) funksiya Ω(g(n)) deyiladi, agar shunday musbat c va N lar mavjud bo’lsaki , barcha n>=N lar uchun f(n)>=cg(n) tengsizlik o’rinli bo’lsa.

Bu ta’rif ham birinchi ta’rifga juda o’xshash, faqat bu yerda tengsizlik teskaridir.

Ta’rifga asosan f(n) funksiya kamida g(n) funksiya kabi o’sadi. Bu ikkita ta’rif yordamida funksiyalar o’rtasida quyidagi munosabatlar o’rinli bo’lishini aniqlash mumkin:

Agar g(n) funksiya O(f(n)) bo’lsa, u holda f(n) Ω(g(n)) bo’ladi.

Yuqoridagi ikkita ta’rifdan foydalanib quyidagio ta’rifni keltirish mumkin.

3-ta’rif. f(n) funksiya Θ(g(n)) deyiladi, agar shunday musbat c1, c2 va N sonlar mavjud bo’lsaki, ular uchun barcha n>=N larda quyidagi tengsizlik o’rinli bo’lsa: c1g(n)<=f(n)<=c2g(n).

Yuqoridagi 2 ta (1,2) ta’riflardan ko’rinib turibdiki, f(n) funksiyaning assimtotik jixatdan yuqoridan va quyidan baxolovchi funksiyalar cheksiz ko’p bo’lishi mumkin. Shuning uchun yuqori chegara bo’lgan holda ularning eng kichigini , quyi chegara bo’lgan holda ularning eng kattasini tanlash kerak bo’ladi. Shunday qilib masalani xal qilib beruvchi algoritmlarni funksiyalarini assimptotik baxolash tartiblarini aniqlash orqali, algoritm samaradorligi aniqlanadi va bir nechta algoritmlardan 1 tasi samarali algoritm sifatida masalani yechish uchun qo’llaniladi.

Foydalaniladigan assimtotik baxolashlardan biri bu OO(g) (ikkita O-katta) bo’lib, u quyidagicha aniqlanadi: f(n) funksiya OO(g(n)) deyiladi agar u O(g(n)) bo’lsa va bunda c-o’zgarmas juda katta bo’lsa, c-o’zgarmas juda katta bo’lsa, masalan 10⁸n funksiya OO(n) bo’ladi, chunki bunda c≥10⁸ bo’lishi kerak. Bu yerda c konstantaning “juda” kattaligi asosan amaliy jixatdan xal qilinayotgan masalaning moxiyatidan kelib chiqqan holda aniqlanadi.