• Odatda ishlatiladigan osish suratlari . Quyidagi diagrammada turli osish suratlari ortasidagi bogliqlik korsatilgan.
    		•

    O'sish tezligi(murakkabligi) nima?




    Download 0,73 Mb.
    Pdf ko'rish
    bet2/6
    Sana22.11.2023
    Hajmi0,73 Mb.
    #103483
    1   2   3   4   5   6
    Bog'liq
    Ma\'ruza 2. Algoritmlar tahlili

    O'sish tezligi(murakkabligi) nima? 
    Kirish ma'lumotlarining hajmiga qarab algoritmning ishlash vaqti ortib borish 
    tezligi o'sish tezligi deb ataladi.
    Aytaylik, siz do'konga mashina va velosiped sotib olish uchun borasiz. Agar siz 
    u erda do'stingizni uchratsangiz va u nima sotib olayotganingizni so'rasa, umuman 
    olganda siz unga mashina sotib olayotganingizni aytasiz. Buning sababi, 
    avtomobilning narxi velosiped narxidan ancha yuqori. 
    Yuqoridagi keltirilgan misolda avtomobil va velosiped narxini funktsiya nuqtai 
    nazaridan qaraylik. Ushbu funktsiya uchun siz nisbatan kichik tartibli xadlariga etibor 
    qaratmaysiz chunki ularning qiymatlari nisbatan kichik bo’lib, yetarlicha katta kirivchi 
    berilganlar qiymati n uchun ahamiyatsiz bo’lib qoladi. 
    Misol tariqasida, n
    4
    , 2n
    2
    , 100n va 500 ba'zi bir funktsiyaning individual 
    xarajatlari bo'lsin, u holda etarlicha katta n uchun umumiy xarajatlar n
    4
    tartibida 
    bo'ladi, chunki n
    4
    xad funksiyasida o'sish tezligi eng kattasi hisoblanadi. 
    500
    100
    2
    )
    (
    2
    4




    n
    n
    n
    n
    f
    Odatda ishlatiladigan o'sish sur'atlari. 
    Quyidagi diagrammada turli o'sish sur'atlari o'rtasidagi bog'liqlik ko'rsatilgan. 
     

    3 

    4 
    Quyida keyingi ma'ruzalarda duch keladigan o'sish tezligining jadvali 
    keltirilgan. 
    Mehnat 
    hajmi 
    Nomi 
    Misol 
    1 
    O’zgarmas 
    Bog'langan ro'yxatning oxiriga yoki 
    boshiga element qo'shish 
    logn 
    Logarifmik 
    Saralangan massivda elementni qidirish 
    n 
    Chiziqlik 
    Saralanmagan massivda elementni 
    qidirish 
    n*logn
    Chiziqlik-
    logarifmik 
    "Bo'l va hukmronlik qil" tamoyili orqali 
    n elementlarni saralash. Birlashtirish orqali 
    saralash 
    n
    2
    Qvadratik 
    Grafning ikki tuguni orasidagi eng qisqa 
    yo'lni topish 
    n
    3
    Qubik 
    Matritsalarni ko'paytirish 
    2
    n
    Exponentsial 
    "Xanoy minorasi" masala 

    Download 0,73 Mb.
    1   2   3   4   5   6




    Download 0,73 Mb.
    Pdf ko'rish