2-mavzu. Algoritmlar samaradorligini baholash Tayanch so’zlar

2-mavzu. Algoritmlar samaradorligini baholash

Tayanch so’zlar: Xotiraviy samara, vaqt samarasi. Algoritmlarning murakkablik darajasi. Algotimlarning taqqoslash usullari.

Reja:

1.Samaradorlik ko’rsatkichlari.

2.Hisoblash qobiliyati

3.Algoritmlarni asimptotik tartiblari .

4. Polinomial vaqt samaradorlik ko'rsatkichi sifatida
1.Samaradorlik ko’rsatkichlari.

Algoritmlarni tahlil qilishning asosiy vazifasi kirish ma'lumotlari hajmining oshib borishi bilan resurslarga bo'lgan talabni (vaqt va xotira xarajatlari) o'lchash usullarini aniqlashdir. Shundan so'ng, o'sish sur'ati qonuniyatlarini tavsiflash uchun zarur bo'lgan matematik mexanizm ishlab chiqiladi. Kirish ma'lumotlari hajmini oshirish bilan turli xil funktsiyalar; "bitta funktsiya boshqasiga qaraganda tezroq o'sadi" iborasi nimani anglatishini aniqlab olishga yordam beradi. Ba'zi hollarda, yaxshi bajarilish vaqtiga erishish yanada murakkab ma'lumotlar tuzilmalaridan foydalanishga bog'liq va bo'lim oxirida biz bunday ma'lumotlar strukturasining juda foydali misolini ko'rib chiqamiz: ustuvor navbatlar va ularni uyum(kucha, heap) asosida amalga oshirish.

Asosiy mavzu - hisoblash muammolarining samarali algoritmlarini izlash. Ushbu umumiylik darajasida kompyuterni hisoblashning butun sohasi ushbu mavzu bilan bog'liq bo'lib tuyuladi; bizning yondashuvimiz boshqalardan qanday farq qiladi? Algoritmlarni ishlab chiqishda umumiy mavzular va loyihalash tamoyillarini aniqlashga harakat qilamiz. Bizni samarali algoritmlarni loyihalashning asosiy usullarini minimal ma'lumot bilan namoyish etuvchi paradigmatik masalalar va usullar qiziqtiradi.

2. Hisoblash qobiliyati

Ko'plab muammolarda uchraydigan yana bir xususiyat - bu ularning asosan diskretligi. Ko'plab muammolarda uchraydigan yana bir xususiyat-bu ularning asosiy ajralib turishi. Boshqacha qilib aytganda, bu shunday masalalarki, ularda yechim kombinatorial variantlarning keng to'plamidan qidirib topiladi; maqsad aniq belgilangan shartlarni qanoatlantiradigan echimni samarali topishdir.

Hisoblash samaradorligi tushunchasini aniqlash uchun, biz birinchi navbatda ish vaqtining samaradorligiga e'tibor qaratamiz: algoritmlar tez ishlashi kerak. Ammo algoritmlar boshqa resursrlardan foydalanish nuqtai nazaridan ham samarali bo'lishi mumkinligini tushunish muhimdir. Xususan, algoritm tomonidan ishlatilinadigan xotira miqdori ham samaradorlikning muhim jixati bo'lishi mumkin.

Algoritm samaradorligi.

(1)T: algoritm samarali deb ataladi agar real kirish ma'lumotlari uchun u tezkor amalga oshirilsa.

(2)T: algoritm samarali deb ataladi agar u sifatli bajarilishni “to’liq qidirish”(полнiy перебор)ga nisbatan tezroq ta'minlasa.

"To'liq qidirish" usuliga qaraganda ancha yaxshi ishlashni ta'minlaydigan algoritmlar, deyarli har doim qimmatli evristik g'oyani o'z ichiga oladi, buning natijasida ushbu yaxshilanishga erishiladi; Bundan tashqari, ular ko'rib chiqilayotgan masalaning ichki tuzilishi va hisoblash qobiliyati haqida foydali ma'lumotlarni taqdim etadilar.

Polinomial vaqt samaradorlik ko'rsatkichi sifatida

Tabiiy kombinatorial masalalarda qidirish vaqti, kirish ma'lumotlari N hajmiga nisbatan eksponensional o'sishga moyildir; agar o'lcham bittaga ko'paysa, unda imkoniyatlar xajmi bir necha marta ko'payadi. Bunday masalalarni yechish uchun yaxshi algoritm yanada samarali miqyoslash modeliga ega bo'lishi kerak; kirish ma'lumotlarining kattalashib borishi bilan o’zgarmas ko’paytuvchiga(aytaylik, ikki baravar) oshishi bilan algoritmning bajarilish vaqti ham qandaydir o’zgarmas S ko’paytuvchiga ko'payishi kerak.

Matematik nuqtai nazardan ushbu masshtablash modelini quyidagicha shakllantirish mumkin. Aytaylik, algoritm quyidagi xususiyatga ega: c> 0 va d> 0 absolyut konstantalar mavjudki, har qanday N xajmli kirish ma'lumotlari to'plami uchun, bajarilish vaqti cN^d sondagi eng sodda operatsiyalar soni bilan chegaralanadi. Boshqacha qilib aytganda, bajarilish vaqti N^d ga proportsionallikdan ko’p emas. Qanday bo'lmasin, ba'zi bir c va d lar uchun bajarilish vaqti ushbu chegaradan oshmaganda, algoritm polinomial bajarilish vaqtini ta'minlaydi deymiz yoki u polinomial vaqtga ega bo'lgan algoritmlar toifasiga kiradi. polinomial vaqtga ega har qanday chegara yuqoridagi masshtablashga ega bo’ladi.

(3)T: Agar algoritm polinomial bajarilish vaqtiga ega bo'lsa, u samarali deb ataladi.

Lekin, polinomial vaqt d ning katta qiymatlarida yaxshi natija bermasligi mumkin, masalan d>=100 holatda bu son juda katta bo’ladi, natijada polinomial bajarilish vaqti kattalashib ketadi. Algoritm ishlayveradi. Bu xolda N^d faqat chegara vazifasini o’taydi.

Polinomial vaqtga ega bo'lgan algoritmlar mavjud bo'lgan masalalar uchun bu algoritmlar deyarli har doim n, n*log n, n^2 yoki n^3 kabi o'rtacha o'sish sur'ati bilan ko'paytuvchilarga mutanosib ravishda ishlaydi. Va aksincha, Polinomial vaqtga ega bo'lmagan algoritmli masalalar uchun bajarilish vaqti juda ham kattalashib ketadi, uni baholash noma'lum bo’ladi, odatda bunday masalalarni yechish juda murakkab bo'lib chiqadi. Umuman olganda, bunday baholashlar ba’zi masalalarda darajaning yoki koeffitsientlarning kattaligi sababli yaxshi natija bermaydi, algoritm yaxshi bo’lsa ham. Ajablanarlisi shuki, aksariyat hollarda polinomial vaqtni matematik aniqlash algoritmlarning samaradorligi va real hayotdagi masalalarni hal qilish bo'yicha kuzatishlarimiz bilan mos keladi. Bunday masalalarni polinomial yechish mumkin bo’lgan masalalar deyiladi. Demak, 3-ta’rifni ma’lum ma’noda talabga javob beruvchi ta’rif desak boladi. U xolda Polinomial vaqtga ega bo'lmagan algoritmlarni qayta ko’rib chiqish kerak.

Polinomial vaqtga ega bo'lgan algoritmlarni ishlab chiqish nima ucgun zarurligini quyidagi jadval ma’lumotlarini tahlil qilib bilish mumkin. Algoritmlarning ishlash vaqtlari

n=	n	n*logn	n^2	n^3	1,5^n	2^n	n!
10
30						18min	10^25y
50					11min	36y	Juda kop
100					12892y	10^17y	----
1000				18min	---	----	----
10000			2min	12kun	--	---	---
100000			3soat	32y	---	---	---
1 mln.		20s	12kun	31710y	---	---	---

3. Asimptotik yuqori chegaralar

Algoritmning samaradorligi bu algoritmni qo’llash uchun qancha kuch talab qilinishini yoki uning qiymati qanchaligini bildiradi. Bunday qiymat har xil mezonlar bilan o’lchanishi mumkin. Bu erda ulardan ikkitasini: vaqt va fazo miqdorinini samaradorlik mezonlari sifatida olinadi. Bunda vaqt mezoni fazodan muhimroq hisoblanadi, shuning uchun samaradorlik asosan ma’lumotlarnu qayta ishlashga ketgan vaqtga nisbatan olinadi. Samaradorlikni baholash uchun mantiqiy birliklar, ya’ni fayl yoki massivning o’lchami n va qayta ishlash uchun ketgan vaqt miqdori t olinadi.

Agar n o’lchov va t vaqt orasida t1=c*n chiziqli bog’liqlik bo’lsa, u holda xajmni bir necha marta, hususan 5 marta, oshirish natijasida, ularni qayta ishlashga ketgan vaqt ham 5 marta oshadi ya’ni n2=5*n bo’lsa, t2=5*t o’rinli bo’ladi. Yoki, agar bog’liqlik t1=logn bo’lsa, u holda n 2 marta oshirilsa vaqt sarfi bor yo’g’i bir birlikka ortadi, ya’ni t2=log2*n=t1+1 bo’ladi. n va t ni bog’liqligini ifodalovchi funksiya odatda murakkab bo’ladi va bunday funksiyani hisoblash katta hajmdagi ma’lumotlarni qayta ishlashda juda muhim hisoblanadi. Hosil qilingan f-ya berilgan funksiyaning tarkibiy samaradorligini bildiradi.Shunga qaramay bu yaqinlashish funksiyaga yaqin hisoblanadi, va katta hajmdagi ma’lumotlar uchun originalga juda yaqin bo’ladi. Samaradorlikning bu o’lchovi assimtotik yaqinlashuvchi o’lchov deyiladi va u samaradorlikni aniqlovchi funksiya ma’lum xadlarini hisobga olganda yoki samaradorlikni aniq hisoblas qiyin, yoki mumkin bo’lmaganda qo’llaniladi.

Agar n o’lchov va t vaqt orasida t1=c*n chiziqli bog’liqlik bo’lsa, u holda xajmni bir necha marta, hususan 5 marta, oshirish natijasida, ularni qayta ishlashga ketgan vaqt ham 5 marta oshadi ya’ni n2=5*n bo’lsa, t2=5*t o’rinli bo’ladi. Yoki, agar bog’liqlik t1=logn bo’lsa, u holda n 2 marta oshirilsa vaqt sarfi bor yo’g’i bir birlikka ortadi, ya’ni t2=log2*n=t1+1 bo’ladi. n va t ni bog’liqligini ifodalovchi funksiya odatda murakkab bo’ladi va bunday funksiyani hisoblash katta hajmdagi ma’lumotlarni qayta ishlashda juda muhim hisoblanadi. Hosil qilingan f-ya berilgan funksiyaning tarkibiy samaradorligini bildiradi.Shunga qaramay bu yaqinlashish funksiyaga yaqin hisoblanadi, va katta hajmdagi ma’lumotlar uchun originalga juda yaqin bo’ladi. Samaradorlikning bu o’lchovi assimtotik yaqinlashuvchi o’lchov deyiladi va u samaradorlikni aniqlovchi funksiya ma’lum xadlarini hisobga olganda yoki samaradorlikni aniq hisoblas qiyin, yoki mumkin bo’lmaganda qo’llaniladi.

Quyidagi misolni ko’ramiz:

n ning kichik qiymatlarida ohirgi had 1000 ning funksiya qiymatini hosil bolishidagi ulushu qolganlariga nisbatan katta hisoblanadi. n=10 bo’lganda 2-xad 100n va ohirgi 1000 xadlar teng bo’ladi va boshqalarga nisbatan funksiya qiymatiga bir xil ta’sir ko’rsatadi. Bu xadlarni funksiya xar bir xadining uning qiymatiga qanday ta’sir qilishining miqyosi n ning har hil qiymatlari uchun quyidagi jadvalda keltirilgan.

Hadlarning funksiya qiymatiga ta’sir qilish miqyosi.

Бахолаш функциялар классификацияси.

Berilgan ikkita f va g funksiyalar uchun quyidagi ta’rifni keltiramiz:

1-ta’rif. f(n) funksiya 0(g(n)) bo’ladi deyiladi, agar shunday musbat c va N sonlar mavjud bo’lsaki , barcha n>=N lar uchun f(n)<=c g(n) tengsizlik bajarilsa.

Bu ta’rifga asosan agar f(n) funksiya 0(g(n)) bo’lsa, u holda uning o’sish tartibi yetarli katta n lar uchun albatta cg(n) funksiya o’sish tartibidan kichik yoki teng bo’lar ekan. Demak, bu holda f(n) funksiya katta n larda cg(n) funksiyadan tez o’sa olmaydi. Bu yerda c va N sonlarini aniqlash muammo bo’lib qoladi, chunki ta’rifda ularni aniqlashning konkret yoli korsatilmagan. Ikkinchidan, bu sonlarga hech qanday shartlar qo’yilmagan. Shuning uchun ularning qiymatlari juda ko’p bo’lishi mumkin

f(n)=2n^2+ 3n+1=O(n^2) (2)

f(n)=2n^2+ 3n+1=O(n^2) (2)

U holda g(n)=n^2 funksiyani tarifdagi funksiya sifatida oluvchi funksiyalardan biri deb xisoblash mumkin. Ta’rifga asosan, c va N lar uchun quyidagi rasmdagi sonlar juftliklarini olish mumkin bo’ladi. (2) funksiya uchun c va N larning qiymatlari.

N va c ning qiymatlarini аniqlash

N va c ning bunday qiymatlarini quyidagi tengsizlikni yechish orqali aniqlanadi:

2n^2+3n+1<=cn^2; (3)

Undan tashqari n ning darajalari bo’yicha ham assimptotik funksiyalarni juda ko’pini olish mumkin. Bu holda eng kichik tartiblisi tanlab olinadi. Bunday noaniqliklarni xal qilish berilgan funksiyadagi kichik tartibli xadlarni barchasini tashlab yuborish va quyidagicha belgilash orqali amalga oshiriladi. Masalan, (1) funksiya uchun

f(n)=n^2+100n+O(log10n)

ko’rinishda olish , (2) funksiya uchun esa f(n)=2n^2+O(n) kabi ko’rinishda olish mumkin bo’ladi.

O- katta funksiyalarning xossalari

Tranzitivlik. Agar f(n) funksiya O(h(n)) bo’lsa, u holda сf(n) funksiya O(h(n)) bo’ladi.

Agar f(n) va g(n) funksiyalarning xar biri O(h(n)) bo’lsa, u holda ularning yig’infisi f(n)+g(n) ham O(h(n)) bo’ladi.

f=an^k funksiya O(n^k) bo’ladi.

f=n^k funksiya ixtiyoriy j>=0 uchun O(n^k+j) bo’ladi.

Agar f(n)=Cg(n) bo’lsa, u holda f(n) funksiya O(g(n)) bo’ladi. Ihtiyoriy a teng emas 1, b teng emas 1 sonlar uchun log(an) funksiya O(log(bn)) bo’ladi.

O- notasiya yordamida funksiyani yuqoridan assimptotik baxolashni ko’rdik. Xuddi shunday baxolashni quyidan ham berish mumkin. Bunday baholashni sigma(Ω) baholash deyiladi va u quyidagicha aniqlanadi:

2- ta’rif. f(n) funksiya Ω(g(n)) deyiladi, agar shunday musbat c va N lar mavjud bo’lsaki , barcha n>=N lar uchun f(n)>=cg(n) tengsizlik o’rinli bo’lsa.

Bu ta’rif ham birinchi ta’rifga juda o’xshash, faqat bu yerda tengsizlik teskaridir.

Yuqoridagi ikkita ta’rifdan foydalanib quyidagio ta’rifni keltirish mumkin.

Ta’rifga asosan f(n) funksiya kamida g(n) funksiya kabi o’sadi. Bu ikkita ta’rif yordamida funksiyalar o’rtasida quyidagi munosabatlar o’rinli bo’lishini aniqlash mumkin:

Ta’rifga asosan f(n) funksiya kamida g(n) funksiya kabi o’sadi. Bu ikkita ta’rif yordamida funksiyalar o’rtasida quyidagi munosabatlar o’rinli bo’lishini aniqlash mumkin:

3-ta’rif. f(n) funksiya Θ(g(n)) deyiladi, agar shunday musbat c1, c2 va N sonlar mavjud bo’lsaki, ular uchun barcha n>=N larda quyidagi tengsizlik o’rinli bo’lsa: c1*g(n)<=f(n)<=c*2g(n).

Misollar

Endi biz bir nechta misollarda assiptotik funcsiyalarni aniqlashni ko’rib chiqamiz.

Sodda sikl yordamida massiv elementlari yig’indisini hisoblashdan boshlaymiz. for (i = sum = 0; i < n; i++) sum += a[i]; Avval 2 ta o’zgaruvchini inisializatsiya qilamiz, sikl n ta iteratsiyadan iborat bo’lib, har bir qadamda yig’indi qiymati sum va i ni qiymati yangilanadi. Demak, algoritm vazifani to’liq yechish uchun 2+2n marta amallar bajarishi kerak bo’ladi, ya’ni bu holda assimptotik funksiya O(n) bo’ladi.

Agar ichma-ich joylashgan sikllar bo’lsa assimptotik funksiya darajasi ham ortib boradi. Buni quyidagi barcha nul holatdan boshlanuvchi massiv ostilarini yig’indisini hisoblash misolida ko’rish mumkin. Uning kodi: for (i = 0; i < n; i++) { for (j = 1, sum = a[0]; j <= i; j++) sum += a[j]; cout<<< i <<Sikl i ni initsializatsiya qilishdan boshlanadi, demak tashqi sikl n marta ishlaydi, va har bir ishlaganda ichki sikldagi 2 ta amal i marta, 3ta amal n marta takroran bajariladi. U holda bajarilgan amallar soni 1+3n + ∑2i=1+3n+n(n-1)=O(n)+ O(n^2) = O(n^2) kabi bo’ladi. Demak, masalani hal qilish uchun O(n^2) tartibdagi sonda amallar bajarilishi kerak.

Agar ichma-ich joylashgan sikllar bo’lsa assimptotik funksiya darajasi ham ortib boradi. Buni quyidagi barcha nul holatdan boshlanuvchi massiv ostilarini yig’indisini hisoblash misolida ko’rish mumkin. Uning kodi: for (i = 0; i < n; i++) { for (j = 1, sum = a[0]; j <= i; j++) sum += a[j]; cout<<< i <<Sikl i ni initsializatsiya qilishdan boshlanadi, demak tashqi sikl n marta ishlaydi, va har bir ishlaganda ichki sikldagi 2 ta amal i marta, 3ta amal n marta takroran bajariladi. U holda bajarilgan amallar soni 1+3n + ∑2i=1+3n+n(n-1)=O(n)+ O(n^2) = O(n^2) kabi bo’ladi. Demak, masalani hal qilish uchun O(n^2) tartibdagi sonda amallar bajarilishi kerak.

Assimptotik funksiyani aniqlash iterasiyalar soni o’zgaruvchan bo’lganda qiyinlashadi. Bu holat quyidagicha misolda ko’rinishi mumkin.

Assimptotik funksiyani aniqlash iterasiyalar soni o’zgaruvchan bo’lganda qiyinlashadi. Bu holat quyidagicha misolda ko’rinishi mumkin.

Elementlari o’sish tartibida joylashgan eng uzun qism massivning uzunligini aniqlash kerak bo’lsin. Masalan, [1 8 1 2 5 0 11 12] massivda tartiblangan elementlardan iborat eng uzun qism massiv [1 2 5] bo’lib, uning uzunligi 3 ga teng. Eng uzun osuvchi qism massivni aniqlash kodi quyidagicha bo’ladi:

for(i=0,length=1; i

for(i1=i2=k =i;k< n-1 &&a[k]

if(length

length =i2-i1 +1;

}

Agar massiv elementlari kamayuvchi bo’lsa, tashqi sikl n-1 marta ishlaydi, xar bir tashqi sikl iterasiyasida ichki sikl 1 marta bajariladi. Demak, bu holda samaradorlik O(n) bo’ladi. Agar elementlar o’suvchi tartibda joylashgan bo’lsa bu algoritm past samara beradi. Chunki bu holda tashqi sikl n-1 marta bajariladi, ichki sikl esa n-1-i xar bir i 0,1,… n-2 uchun, demak, bu xolda algoritm samaradorligi O(n^2) bo’ladi

Agar massiv elementlari kamayuvchi bo’lsa, tashqi sikl n-1 marta ishlaydi, xar bir tashqi sikl iterasiyasida ichki sikl 1 marta bajariladi. Demak, bu holda samaradorlik O(n) bo’ladi. Agar elementlar o’suvchi tartibda joylashgan bo’lsa bu algoritm past samara beradi. Chunki bu holda tashqi sikl n-1 marta bajariladi, ichki sikl esa n-1-i xar bir i 0,1,… n-2 uchun, demak, bu xolda algoritm samaradorligi O(n^2) bo’ladi

Eng yahshi, o’rtacha va eng yomon algoritmlar.

Yuqoridagi misollarga asoslanib shuni aytish mumkinki, algoritmlar samaradorligi bo’yicha 3 hil bolishi mumrin: 1) Eng yomon holat bunda algoritm masalani echish uchun maksimal sondagi amallarni bajarishni talab qiladi; 2) Eng yaxshi holat bunda algoritm masalani echish uchun minimal sondagi amallarni bajarishni talab qiladi; 3) Ortacha holat bunda algoritm masalani echish uchun maksimal va minimal sonlar orasidagi sondagi amallarni bajarishni talab qiladi.

Sodda hollarda ortacha samaradorlikni aniqlash algoritmga mumkin bolgan kirishlar, har bir kirish uchun algoritm asosida bajarilayotgan etaplar sonini aniqlash, barcha kirishlar uchun qadamlar sonini aniqlash va ularning hammasini qoshib hisoblangandan song kirishlar soniga bolish yordamida amalda oshiriladi.