Mavzu: Algoritmlar samaradorligini tahlil qilish. Reja: Samaradorlik ko’rsatkichlari

Mavzu: Algoritmlar samaradorligini tahlil qilish. Reja: Samaradorlik ko’rsatkichlari

Mavzu: Algoritmlar samaradorligini tahlil qilish.

Reja:

1. Samaradorlik ko’rsatkichlari.

2. Hisoblash qobiliyati

3. Algoritmlarni asimptotik tartiblari .

4. Polinomial vaqt samaradorlik ko'rsatkichi sifatida

5. Algoritmik samaradorlik.

Foydalanilgan adabiyotlar.

1. Algoritmlarni tahlil qilishning asosiy vazifasi kirish ma'lumotlari hajmining shib 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

Algoritmlarni baholash uchun ko’pgina mezonlar mavjud. Odatda kirituvchi berilganlarni ko’payishida masalani yechish uchun kerak bo’ladigan vaqt va xotira hajmlarini o’sish tartibini aniqlash muammosi qo’yiladi. Har bir aniq masala bilan kiritiladigan berilganlarni miqdorini aniqlovchi qandaydir sonni bog’lash zarur. Bunday son masalaning kattaligi deb qabul qilinadi. Masalan, ikkita matritsani ko’paytirish masalasining o’lchami bo’lib, matritsalar kattaligiga xizmat qilishi mumkin. Graflar haqidagi masalada o’lcham sifatida graf shohlarining soni bo’lishi mumkin. Algoritm sarflanayotgan vaqt masalaning o’lchami funksiyasi sifatida algoritmni vaqt bo’yicha qiyinligi deb nomlanadi. Bunday funksiyaga masalaning kattaligi oshganda limit ostidagi o’zgarish asimptotik qiyinlik deb aytiladi. Shunga o’xshab, hajmiy qiyinlik va asimptotik hajmiy qiyinlikni aniqlash mumkin. Aynan algoritmning asimptotik qiyinligi natijada shu algoritm yordamida nyechiladigan masalarni kattaligini aniqlaydi. Agar algoritm n kattalikdagi kirishlarni 2 С vaqtda qayta ishlasa (c-const), unda algoritmning vaqt bo’yicha qiyinligi ( ) 2 O n teng deb hisoblanadi, va n tartibda deb aytiladi. Hisoblash mashinalar tezligi oshishiga qaramasdan, ular yordamida yechilayotgan masalalar kattaligini oshishini algoritm qiyinligini tahlil orqali aniqlaydi. Faraz qilaylik, A1,A2,…,A5 nomli 5 ta algoritm quyidagi vaqtli qiyinliklar bilan berilgan.