• 1) Algoritm murakkabligini statik va dinamik o‘lchovlari. Vaqt va xotira hajimi bo‘yicha qiyinchiliklar.
  • 3) Algoritmlarni vaqt va hajmiy marakkabligini baholashda tekis va logorifmik solishtirma mezonlari.
  • 1-mustaqil ishi qarshi shahar-2024




    Download 82,06 Kb.
    bet1/19
    Sana13.05.2024
    Hajmi82,06 Kb.
    #230432
      1   2   3   4   5   6   7   8   9   ...   19
    Bog'liq
    1-MUSTAQIL ISHI


    MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI QARSHI FILIALI TELEKOMUNIKATSIYALAR FAKULTETI
    TT-13-21-S-GRUHI TALABASI ARSLONOV JAMSHIDBEKNING ALGORITIMLARNI LOYXALASH FANIDAN

    1-MUSTAQIL ISHI



    QARSHI SHAHAR-2024

    Algoritm murakkabligining statik va dinamik o‘lchovlari. Vaqt va xotira hajmi bo‘yicha qiyinchiliklar Algoritmlarni eng yomon va o‘rtacha holatlarda baholash. Algoritmlarni vaqt va hajmiy murakkabligini baholashda tekis va logorifmik solishtirma mezonlari. Ketma – ketliklar, to’plamlar, daraxtlar, graflarni ifodalash usullari. Taqribiy integrallash usullarini aniqligi va hisoblash hajmi bo‘yicha taqqoslash. Algebraik va transtsendent tenglamalarni taqribiy yechish usullarini yaqinlashish tezligi bo‘yicha baholash
    REJA:

    1) Algoritm murakkabligini statik va dinamik o‘lchovlari. Vaqt va xotira hajimi bo‘yicha qiyinchiliklar.

    2) Algoritmlarni eng yomon va o‘rtacha xolatlarda baholash

    3) Algoritmlarni vaqt va hajmiy marakkabligini baholashda tekis va logorifmik solishtirma mezonlari.


    Algoritmning vaqt murakkabligini baholash. Algoritmlar murakkabligi funksiyalarining turlari
    Doimiy vaqt
    Algoritmga algoritm deyiladi doimiy vaqt(vaqt sifatida qayd etilgan O (1)) qiymat bo'lsa T(n) kirish hajmiga bog'liq bo'lmagan qiymat bilan cheklangan. Masalan, massivda bitta elementni olish doimiy vaqtni oladi, chunki uni topish uchun bitta buyruq bajariladi. Biroq, tartiblanmagan massivda minimal qiymatni topish doimiy vaqtdagi operatsiya emas, chunki biz massivning har bir elementini skanerlashimiz kerak. Shunday qilib, bu operatsiya chiziqli vaqtni oladi, O (n). Agar elementlarning soni oldindan ma'lum bo'lsa va o'zgarmasa, bunday algoritmni doimiy vaqt algoritmi deb atash mumkin.
    "Doimiy vaqt" nomiga qaramay, ish vaqti vazifa hajmidan mustaqil bo'lishi shart emas, lekin ish vaqtining yuqori chegarasi bo'lmasligi kerak. Masalan, "qiymatlarni almashish" vazifasi a va b, zarur bo'lsa, natijada biz olamiz ab", doimiy vaqt muammosi hisoblanadi, garchi algoritmning ishlash vaqti tengsizlikning mavjudligiga bog'liq bo'lishi mumkin. a ≤ b yoki yo'q. Biroq, ma'lum bir doimiylik mavjud t, ular uchun vazifani bajarish vaqti har doim oshmaydi t.
    Quyida doimiy vaqtda ishlaydigan ba'zi kod misollari keltirilgan:
    Int indeksi = 5; int element = ro'yxat; agar(shart to'g'ri) keyinboshqa doimiy ish vaqti bilan ba'zi operatsiyalarni bajarish uchun i = 1 uchun 100 uchun j = 1 uchun 200 doimiy ish vaqti bilan ba'zi operatsiyalarni bajaradi
    Agar T(n) bu O ( ba'zi doimiy qiymat), bu ga teng T(n) O (1) dir.

    Download 82,06 Kb.
      1   2   3   4   5   6   7   8   9   ...   19




    Download 82,06 Kb.

    Bosh sahifa
    Aloqalar

        Bosh sahifa



    1-mustaqil ishi qarshi shahar-2024

    Download 82,06 Kb.