• O‘sishning asimptotik tartibi
    		•

    Reja Algoritmlarning tahlili




    Download 247,61 Kb.
    Pdf ko'rish
    bet2/8
    Sana23.05.2024
    Hajmi247,61 Kb.
    #251662
    1   2   3   4   5   6   7   8
    Bog'liq
    5-Ma’ruza. Algoritmlar samaradorligini baholash

    Algoritm samaradorligi
    . 
    1) algoritm samarali deb ataladi agar real kirish ma’lumotlari uchun u tezkor 
    amalga oshirilsa. 
    2) algoritm samarali deb ataladi agar u sifatli bajarilishni “to’liq qidirish” ga 
    nisbatan tezroq ta‘minlasa. 
    O‘sishning asimptotik tartibi 
    Demak, yuqoridagi hisoblashlarning ruxsat etiganligidan kelib chiqqan 
    holda, n o‘lchamli kirish ma’lumotlari uchun algoritmning yomon bajarilish vaqti 
    qaysidir f(n) funksiyaga proporsional ravishda o‘sishga ega bo’lar ekan. f(n) 
    funksiya algoritm bajarilish vaqtini baholashning chegarasi bo‘ladi (ya’ni undan 
    oshib ketmaydi).
    Algoritmlar asosan psevdokod shaklida keltiriladi. Algoritmning bajarilish 
    vaqtini baholash chegarasini hisoblash orqali biz psevdokodda bajariladigan 
    qadamlar sonini aniqlaymiz. Masalan, bitta qadam o’zgaruvchiga qiymat 
    o‘zlashtirish, massivdan element qidirish, ko‘rsatkich bo‘yicha o‘tish yoki 
    belgilangan o‘lchamdagi butun son ustida arifmetik amal bajarish. Agar n o‘lchamli 
    kiruvchi ma’lumotlar uchun algoritmning bajarilish vaqti haqida so‘z boradigan 
    bo’lsa, u holda misol tariqasida quyidagicha fikr bildirilishi mumkin: “Ixtiyoriy n 
    o’lchamli kiruvchi ma’lumotlar uchun bu algoritm 1.62n^2+3,5n+8 qadamdan 
    oshmagan holda bajariladi”. 
    Bilamizki, algoritmning psevdokodlarda ifodalanishi yuqori dasturlash 
    tillarida ifodalanishga yaqin. Undagi har bir qadam dastur kompilyatsiyasida 
    primitive qadamlardan tashkil topgan. Ushbu primitive qadamlar ham hisoblashlar 
    jarayonida o’z navbatida aniq arxitektura asosida yanayam ko’proq qadamlarga 
    ajratiladi. 
    Shunday qilib, qat’iy ravishda shuni aytish mumkinki – masalani hisoblash 
    abstraksiyasining turli xil darajalarida ko’rib chiqish jarayonida “qadam” 

    tushunchasi doimiy koeffitsiyent yordamida ortishi yoki kamayishi mumkin. 
    Masalan, yuqori darajadagi tilda bitta amalni bajarish uchun 25 ta quyi darajali 
    mashina kodi bajarilishi talab etilsa, u holda bizning maksimum 1.62n^2+3,5n+8
    qadamdan iborat algoritmimiz fizik qurilma darajasiga yaqin darajada tahlil 
    qilinganda 40,5n^2 + 87,5n + 200 qadam bilan bajariluvchi algoritm sifatida 
    qaraladi. 

    Download 247,61 Kb.
    1   2   3   4   5   6   7   8




    Download 247,61 Kb.
    Pdf ko'rish