5-Ma’ruza. Algoritmlar samaradorligini baholash. Iteratsion sikllar.
Reja
1. Algoritmlarning tahlili.
2. O‘sishning asimptotik tartibi.
3. Algoritmlarning murakkablik sinflari.
4. Algoritmning hajmiy murakkabligi.
5 Algoritmning resurs bo’yicha samaradorligini baholash usullari.
Algoritmlarning tahlili
Algoritmlarni tahlil qilishda asosiy masala – kirish ma’lumotlari hajmining
ortishi bilan resurslarga (vaqt va hotira sarfiga) bo’lgan talabning masshtablashishi
qonunining paydo bo’lishi hisoblanadi. Aniq holatlar
hisoblash chegarasi
mazmunini tushunishga yordam bergani sababli ushbu konsepsiya aniq hollarda
qanday qo’llanilishi ko’rib chiqish lozim. Shundan so’ng kiruvchi ma’lumotlarning
ortishi bilan turli xil funksiyalar bajarilish tezligi o’zgarishining qoidasini yozuvchi
matematik mexanizm ishlab chiqiladi.
Polinomial vaqt samaradorlik belgisi sifatida
qaraladi. Analitiklar diskret algoritmlarning tahlili (bu izlanish sohasi 1960-yillarda
yuqori templarda rivojlana boshladi) bilan shug’ullanishni
boshlaganda ularda
ya’ni qanday miqdoriy baholash yordamida “aqlli” bajarilish vaqti konsepsiyasini
ifodalash mumkinligi to’g’risida konsepsus paydo bo’la boshladi. Odatiy
kombinatorika masalalarida qidirish vaqti N kiruvchi ma’lumotlarning o’lchamiga
nisbatan eksponensial o’sishiga
asoslangan; agar o’lcham birga oshsa,
u holda
ehtimollik ham multiplikativ ravishda oshadi. Bunday masalalarda kirish
ma’lumotlari o’lchamining doimiy kattalikka oshishi
algoritmning bajarilish
vaqtining C doimiy kattalikka oshirishi lozim.
Sekundiga millionlagan yuqori darajadagi buyruqlar bajaradigan protsessor
mavjud deb tasavvur qiladigan bo’lsak, u holda bajarilish vaqti chegaralari n, n
〖
𝑙𝑜𝑔〗
_2n, n^2 , n^3 , 1.5^n , 2^n va n! bo’lgan algoritmlar uchun kiruvchi
ma’lumotlar turli bo’lganda ushbu algoritmlarning
bajarilish vaqti jadvali
keltirilgan.
Algoritmning ishlash vaqti 1025 yildan oshgan hollarda jadval yacheykasi “-
--” bilan to’ldirilgan.
