|
Reja Algoritmlarning tahliliBog'liq 5-Ma’ruza. Algoritmlar samaradorligini baholashN
2
Algoritmning bajarilish vaqti kvadratik bo’lishi uni amaliyotda
kamroq masalalarni yechishda foydali bo’lishini anglatadi.
Odatda, kvadratik bajarilish vaqti ma’lumotlarnining barcha
elementlarini juft holatda qayta ishlanishida hosil bo’ladi (ikki
darajali ichma-ich sikllarda bo’lishi mumkin).
N
3
Ma’lumotlar elementlarini uch marta qayta ishlovchi (ichma-ich
joylashgan uch darajali sikl bo’lishi mumkin) algoritmlar kubik
bajarilish vaqtiga ega va ular amaliyotda juda kam masalalar
uchun qo’llaniladi. N=100 bo’lganda, bajarilish vaqti bir
millionga teng. N ikkilanganda esa bajarilish vaqti sakkiz marta
oshadi.
2
N
Bir nechta eksponensial bajarilish vaqtiga ega algoritmlar
amaliyotda qo’llaniladi. Bunday algoritmlar masalani to’gridan
to’g’ri yechishda tabiiy ravishda yuzaga keladi, masalan to’liq
me’yordan oshishda. N=20 ga teng bo’lganda bajarilish vaqti bir
millionga teng bo’ladi. N ikkilanganda bajarilish vaqti
eksponensial ravishda ortadi.
Algoritm bajarilishidagi hotiraning holati belgilangan qismlarni joylash
uchun talab qilinadigan qiymatlar bilan belgilanadi. Bunda masalani yechish
jarayonida qo’shimcha yacheykalardan foydalanishi mumkin. A algoritmning D
kirishlari uchun talab qilinadigan
hotira hajmi
deganda, algoritmning bajarilishi
jarayonida maksimal sondagi foydalanilgan hotira yacheykalari tushuniladi.
Algoritmning hajmiy murakkabligi
algoritmning hotira hajmi funksiyasini
asimptotik baholashning eng yomon holati bilan ko’rib chiqiladi.
Shundan kelib chiqqan holda
algoritmning resurs bo’yicha murakkabligi
yomon, o’rta va yaxshi holatlar uchun vaqt va hajmiy murakkabliklari funksiyalari
(qaralayotgan holatga mos asimptotik qiymati bilan berilgan) sinflarining juftligini
tartiblangan ketma-ketligi bilan belgilanadi.
|
| |
