5 mavzu: algoritmlar va ularning qiyinligi reja Algoritmni baholash mezonlari

5 - MAVZU: ALGORITMLAR VA ULARNING QIYINLIGI
Reja

1. Algoritmni baholash mezonlari.

2. Algoritmni vaqt qiyinligi bo’yicha optimallashtirish.

3. Algoritmni hajmiy qiyinligi bo’yicha optimallashtirish.

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 yechiladigan masalarni kattaligini aniqlaydi. Agar algoritm n kattalikdagi kirishlarni  vaqtda qayta ishlasa (c-const), unda algoritmning vaqt bo’yicha qiyinligi  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.

Algoritm	Vaqtli qiyinlik
A1
A2
A3
A4
A5