• Omega notatsiya
  • Teta notatsiya
  • Algoritmlar samaradorligini hisoblash
  • Bajardi: Musurmonov Umid Tekshirdi




    Download 122.48 Kb.
    bet4/13
    Sana01.12.2023
    Hajmi122.48 Kb.
    #109162
    1   2   3   4   5   6   7   8   9   ...   13
    Bog'liq
    Ma\'lumotlar tuzilmasi 1-mustaqil ish
    rtser, elsthrough-reading, 1. Arab xalifaligining tashkil topishi va taraqqiyot bosqichlari, 1-mavzu. Matrisa va ular ustida amallar, use-of-interactive-methods-in-expressing-motion-equations-in-different-coordinate-systems, пул ва банклар фанидан ЯН саволлари 2023 2024
    Katta O notatsiya. f(x)=O(g(n)) deb belgilanadi, faqat va faqat shunday musbat c va m konstanta mavjud bo’lib, f(n)<=c*g(n) tengsizlik o’rinli bo’lsa, barcha n, n>=m holatlarda.


    Masalan, ushbu funksiyani 3n+2=O(n)deb olish mumkin,chunki 3n+2<=4n, n>=2 tengsizlik o’rinli.
    Ushbu funksiyani6*2n+n2=O(2n) deb olish mumkin,chunki 6*2n+n2<=7*2nifoda o‘rinli,barcha n>=4 larda. O(1) deb hisoblash vaqti o’zgarmas bo’lgan holatni belgilaymiz. O(n2ni kvadratik, O(n3) ni kubik, O(2n) ni eksponensial deb ataladi. Agar algoritmni bajarilish vaqti O(log n) bo‘lsa, O(n) ga qaraganda tezkor algoritm deb hisoblanadi.



    • Omega notatsiya. f(x) = Ω(g(n)) deb belgilanadi, faqat va faqat shunday musbat c va m konstanta mavjud bo’lib, f(n)<=c*g(n) tengsizlik o’rinli bo’lsa, barcha n, n>=m holatlarda.


    Masalan, 3n+2=Ω(n) deb belgilash mumkin, chunki 3n+2>=3n, n>=1 tengsizlik o’rinli.6*2n+n2=Ω (2n) deb olish mumkin,chunki 6*2n+n2>=6*2n ifoda o‘rinli,barcha n>=1 larda.




    • Teta notatsiya. f(x) = θ (g(n)) deb belgilanadi, faqat va faqat shunday musbat c va m konstanta mavjud bo’lib, c*g(n)<= f(n)<=c2*g(n) tengsizlik o’rinli bo’lsa, barcha n, n>=m holatlarda.


    Masalan, 3n+2= θ (n) deb belgilash mumkin, chunki 3n+2>=3n, n>=1va 3n+2<=4nbarcha n>=2 da tengsizlik o’rinli. 6*2n+n2=θ (2n) deb olish mumkin,

    Algoritmlar samaradorligini hisoblash
    Algoritmlar samaradorligini hisoblashda kirish ma’lumotini qanday tanlash ko’rilayotgan algoritmni bajarilishiga yaxshigina ta’sir ko’rsatadi.Masalan, agar kirish ma’lumotlari allaqachon saralangan bo‘lsa, ba’zi saralash algoritmlari juda yaxshi ishlaydi, ayrimlari ancha past samaradorlik bilan ishlashi mumkin. Agar kirish ma’lumotlari saralanmagan, tartibsiz bo’lsa, buni aksi bo’lishi mumkin.Shuni e’tiborga olgan holda, algoritmlar taxlil qilinishi kerak.

    1   2   3   4   5   6   7   8   9   ...   13




    Download 122.48 Kb.

    Bosh sahifa
    Aloqalar

        Bosh sahifa



    Bajardi: Musurmonov Umid Tekshirdi

    Download 122.48 Kb.