4-mustaqil ish mavzu: Tartibsizlik matritsasi (confusion matrix) Guruh: kif 20-03 Bajardi: Keldibekov Azamat Mavzu

f(n)=2n^2+ 3n+1=O(n^2) (2)
f(n)=2n^2+ 3n+1=O(n^2) (2)
U holda g(n)=n^2 funksiyani tarifdagi funksiya sifatida oluvchi funksiyalardan biri deb xisoblash mumkin. Ta’rifga asosan, c va N lar uchun quyidagi rasmdagi sonlar juftliklarini olish mumkin bo’ladi. (2) funksiya uchun c va N larning qiymatlari.
N va c ning qiymatlarini аniqlash
N va c ning bunday qiymatlarini quyidagi tengsizlikni yechish orqali aniqlanadi:
2n^2+3n+1<=cn^2; (3)
Undan tashqari n ning darajalari bo’yicha ham assimptotik funksiyalarni juda ko’pini olish mumkin. Bu holda eng kichik tartiblisi tanlab olinadi. Bunday noaniqliklarni xal qilish berilgan funksiyadagi kichik tartibli xadlarni barchasini tashlab yuborish va quyidagicha belgilash orqali amalga oshiriladi. Masalan, (1) funksiya uchun
f(n)=n^2+100n+O(log10n)
ko’rinishda olish , (2) funksiya uchun esa f(n)=2n^2+O(n) kabi ko’rinishda olish mumkin bo’ladi.
O- katta funksiyalarning xossalari
Tranzitivlik. Agar f(n) funksiya O(h(n)) bo’lsa, u holda сf(n) funksiya O(h(n)) bo’ladi.
Agar f(n) va g(n) funksiyalarning xar biri O(h(n)) bo’lsa, u holda ularning yig’infisi f(n)+g(n) ham O(h(n)) bo’ladi.
f=an^k funksiya O(n^k) bo’ladi.
f=n^k funksiya ixtiyoriy j>=0 uchun O(n^k+j) bo’ladi.
Agar f(n)=Cg(n) bo’lsa, u holda f(n) funksiya O(g(n)) bo’ladi. Ihtiyoriy a teng emas 1, b teng emas 1 sonlar uchun log(an) funksiya O(log(bn)) bo’ladi.
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.
Yuqoridagi ikkita ta’rifdan foydalanib quyidagio ta’rifni keltirish mumkin.
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:
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: