Tahlil qilishdan maqsad. Asimptotik Tahlil Algoritmlarni tahlil qilishda notatsiya tizimi

Algoritm tahlili

Reja:

1. 
   Tahlil qilishdan maqsad.
   
2. 
   Asimptotik Tahlil
   
3. 
   Algoritmlarni tahlil qilishda notatsiya tizimi
   

Dastur tuzish jarayonida uning ko'p taraflariga e'tibor berish kerak: modullilik, qulay interfeyslilik, xavfsizlilik, tushunarlilik va b.q. Dasturningning ishlash davomida o'zini tutishi (performance) esa dasturning barcha muhim jihatlaridanda muhimroqdir. Chunki,dasturni qotib qolmasdan ishlashi va doim to'g'ri natijalar berishi uning asosiy vazifasidir. Dastur uchun eng yaxshi unumdorlikni tanlash uchun esa unda foydalaniladigan algoritmni dastlab Tahlil qilib ko'rish kerak.

Ikkita algoritm berilgan, qaysi biri yaxshiroq ekanligini qanday aniqlash mumkin?

Eng oddiy yo'li, dasturni ikkita kompyuterda ishga tushirib dasturga turli sonlar kiritish bilan tekshirib ko'rish va qaysi birini kam vaqt olayotganini aniqlash. Ammo, bu usulning juda ko'p kamchiliklari mavjud:

1) Ba'zi sonlar uchun birinchi algoritm, ba'zi sonlar uchun esa ikkinchi algoritm tezroq ishlashi mumkin.

2) Ba'zi sonlar uchun birinchi kompyuterdagi birinchi algoritm, ba'zi sonlar uchun esa ikkinchi algoritm boshqa kompyuterda tezroq ishlashi mumkin.

Algoritmni asimptotik Tahlil qilish yuqoridagi muammolarni bartaraf etishga yordam beradi. Algoritmni asimptotik Tahlil qilishda biz algoritmga turli sonlar kiritilganda u qanday unumdorlik ko'rsatishini baholaymiz. Biz algoritmga kiritilayotgan sonlar ortishi bilan uning ishlash vaqti (yoki xotiradan joy egallashi) qanday ortishini o'lchaymiz (algoritmni ishlash vaqt davomiyligi qanchaligini emas).

Asimptotik Tahlil algoritmni baholash uchun eng yaxshi variantmi?

Asimptotik Tahlil 100% to'g'ri tahlil qilish imkonini bermaydi, ammo algoritmini asimptotik Tahlil qilish mavjud boshqa barcha Tahlil yo'llari ichida eng yaxshisi. Misol uchun, ikkita saralash algoritm bor deb tassavur qilaylik, birinchisiga n son kiritilganda uning ishlash vaqti 100nLog(n) funksiya asosida, ikkinchisiga n son kiritilganda uning ishlash vaqti 2nLog(n) funksiya asosida ortsin. Bu algoritmlarning unumdorligi asimptotik Tahlilda teng deb hisoblanadi (o'sish tartibi nLog(n)), chunki asimptotik Tahlilda konstanta koeffisiyentlar hisobga olinmaydi.

Asimptotik Tahlil

O'tgan postda biz asimptotik Tahlil nima ekanligi bilan tanshgan edik, Ushbu postda biz chiziqli qididiruv algoritmini asimptotik Tahlil qilamiz.

Algoritmni Tahlil qilishda 3 xil holat bo'lishi mumkin:

1) Eng yomon holat

2) O'rtacha holat

3) Eng zo'r holat

Quyida chiziqli qidiruv algoritimining realizatsiyasi keltirilgan:

#include

int search(int arr[], int n, int x)

{

int i;

for (i=0; i{

if (arr[i] == x)

return i;

}

return -1;

}

int main()

{

int arr[] = {1, 10, 30, 15};

int x = 30;

int n = sizeof(arr)/sizeof(arr[0]);

printf("%d soni %d inchi indexda topildi", x, search(arr, n, x));

getchar();

return 0;

}

Eng yomon holat

Eng yomon holatda biz algoritmni eng ko'p vaqt oladigan holatini qaraymiz. Bu holat — eng baland chegara (Upper bound) deb ham ataladi. Chiziqli qidiruv algoritmida eng yomon holat — qidirilayotgan x son arr massivda mavjud bo'lmasligi. Chunki, agar arr massivda qidirilayotgan element mavjud bo'lmasa, search() funksiyasi massivni barcha elementlarini bilan bitta-bitta qarab chiqadi. Ushbu turdagi Tahlil eng keng foydalaniladi.

O'rtacha holat

O'rtacha holatda algoritmni ishlash vaqtini topish uchun, barcha sonlarni topish uchun ketgan vaqtlarni (har bir sonni alohida-alohida topishga ketgan vaqtlar) o'rta arifmetigi olinadi. Odatda amaliyotda, bu Tahlil juda ham ko'p ishlatilmaydi, chunki bu holtda biz programma qabul qilishi mumkin bo'lgan barcha qiymatlarni bilishimiz kerak bo'ladi.

Eng zo'r holat

Eng zo'r holat bu algoritmni bajarilishi uchun ketgan eng kam vaqtli holatdir. Chiziqli qidiruv algoritimida, agar qidirilayotgan son massivda birinchi bo'lib turgan bo'lsa sodir bo'ladi. Bu turdagi Tahlil amaliyotda deyarli umuman ishlatilmaydi, chunki eng zo'r holat faqat shartli sonlardagina bajarilishi mumkin.

Esda tuting: Algoritmlarni asimptotik Tahlil qilishda odatda eng yomon holat Tahlilidan foydalaniladi. Ya'ni algoritmning ishlash vaqti uning eng yomon holati bilan baholanadi.

Algoritmlarni tahlil qilishda notatsiya tizimi

Algoritmning murakkabligini batafsilroq tahlil qilishda, N uzunlikning bitta kirishida algoritm tomonidan bajarilgan elementar operatsiyalar soni har doim ham bir xil uzunlikning boshqa kiritishida bajarilgan ishlar soni bilan bir xil emasligi ayon bo'ladi. Bu ushbu algoritmning murakkablik funktsiyasining sobit uzunlikdagi ma'lumotlarga xatti-harakatlarini aks ettiruvchi maxsus belgi qo'yish zarurligiga olib keladi.

D_A rasmiy tizimda berilgan ushbu vazifaning o'ziga xos muammolarining to'plami bo'lsin. D D_A muayyan muammoning vazifasi bo'lsin va | D | = N. Umumiy holda, N kuchining barcha o'ziga xos muammolarini o'z ichiga olgan D_A to'plami mavjud:

ushbu to'plamni DN tomonidan belgilang:

D_N = {D D_N,: |D| = N};

tomonidan o'rnatilgan DN quvvatini belgilang

M_DN > M_DN = |D_N |.

Keyinchalik, mazmunli ravishda, N o'lchovining turli muammolarini echgan holda, ushbu algoritm ba'zi hollarda eng ko'p operatsiyalarni bajaradi, ba'zi holatlarda esa eng kam sonli operatsiyalarni bajaradi. Biz quyidagi belgini olib boramiz:

1. 
   F_a(N) - N o'lchovining aniq muammolarini hal qilish uchun A algoritmi tomonidan bajariladigan operatsiyalarning eng katta miqdori:
   

F_a(N) = max {F_a (D)} - eng yomon ish D_N

2. 
   F_a(N) - - eng yaxshi holat - N o'lchovining aniq muammolarini hal qilish uchun A algoritmi tomonidan bajariladigan operatsiyalarning eng kam soni:
   

F_a(N) = min {F_a (D)} - eng yaxshi holat D_N

3. 
   F_a (N) - o'rtacha holat bu N o'lchovining aniq muammolarini echish uchun A algoritmi tomonidan bajarilgan operatsiyalarning o'rtacha soni:
   

F_a(N) = (1 / M_DN)* {F_a (D)} - o'rtacha holat D_N
Adabiyotlar ro’yxati

4. 
   Gulomov S.S. va boshqalar. Axborot tizimlari va texnologiyalari. Toshkent,
   2000
   
5. 
   Ахо А., Хопкрофт Дж. Построение и анализ вычислительных алгоритмов.- М: Мир, 1979 г., 535 с.
   
6. 
   Вирт Н.. Алгоритмы и структуры данных. – Досса, Хамарайан, 1997.
   
7. 
   Кнут Д. Искусство программирования для ЭВМ. Основные алгоритмы.-М:Мир, 2000 г.
   
8. 
   Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.:МЦНМО, 2001.- 960 с.
   
9. 
   Лебедев В.И. Введение в системы программирования. М: Статистика,
   1975