Alqoritm analizi və Asimtotik analiz (Analysis of Algorithms | Asymptotic Analysis)

Salam. Algoritm nədir, algoritmin növləri və xassələr haqqında məlumatları bu məqalədə sizinlə paylaşmışdım. Bu məqalədə isə alqoritm analizi və asimtotik analiz haqqında müəyyən məlumatları sizinlə bölüşmək istiyirəm. Algoritmlərin analizi zamanı algoritmin istifadəçi dostu olması (user friendliness), moduluyarlığı (modularity), təhlükəsizliyi (security) və başqa bu kimi bir qurup şərtlərə baxılır. Ancaq bu şərtlər o vaxt bizim üçün əhəmiyyət kəsb edirki bu alqoritm bizə lazım olan  effektivliyi (performance) verə bilsin. Effektivlikdən qəsdimiz algoritmin icra olunma müddəti (Time Complexity) və icra zamanı nə qədər yaddaş sahəsi (Space Complexity) istifadə etməsidir. Bəzən bir məsələnin həlli üçün birdən çox (nümunə olaraq sıralama üçün Selection Sort,Insertion Sort,Heap Sort,Merge Sort,Quick Sort,Bubble Sort algoritmlərini görsətmək olar) algoritm mövcut olur. Bu zaman məsələnin həlli üçün hansı algoritmin daha yaxşı olması kimi sualla qarşılaşırıq. Bunun bir yolu mövcut algoritmləri yazaraq hansının daha sürətli, daha az yaddaş sahəsi ayırmasını yoxlamaqdır. Bu üsul düzgün görünsədə elmi yanaşma olmamaqla bərabər, real vəziyyətidə əks etdirməyəcək. Çünki, sizin sınağınız mühitdən (prosessorun güçündən, RAM-ın ölçüsündən) aslı olacaq və daha böyük məlumatlarla işlədikdə hansı nəticəni verəcəyini bilmədiyinizdən düzgün olmayacaq. Bu problemin həlli üçün mürəkkəblik teoremindən(complexity theory) istifadə olunur. Biz bu teoremdə yer alan üç mürəkkəblik sinifini (notation) istifadə edəcəyik. Bunlar:

ØWorst Case (en pis hal) à big-o  

ØAverage Case (orta halı) à Theta Θ

ØBest Case (ən yaxşı halı) à big-Ω

Big-O notation

Algoritmin ən pis halda nə qədər icra olunacaqağını müəyyən etmək üçün istifadə olunur. Daha aydın olması üçün, n elementdən ibarət sırasız massivdə, hər hansı bir dəyərin axtarılması zamanı, həmin dəyərin massivin sonuncu indeksində yerləşən dəyəri olmasını göstərə bilərik. Bu zaman ən pis hal O(N) olcaq. Digər nümunəmiz ədədin tək və cüt olması algoritminin Big-O -sunu hesablamaqdır. Hər bir halda algoritm bir dəfə icra olunacağı üçün O(1) olcaq. Aşağıdakı nümunələr tam aydın olmasına kömək edəcək

İç içə dövr sayı artdıqca uyğun olaraq O(N3), O(N4) olacaq

İkili axtarışın (Binary search) ən pis halı O(log N) olacaq.Loqarifmik dəyişməni "Heap sort" algoritminin izahı zamanı görəcəyik.

Big O notasiyası (notation) riyazi olaraq aşağıdakı formada təsvir edilir.

|f(x)|  = O(g|(x)|)

|f(x)| < C*|g(x)|
Düsturu izah edəsi olsaq: f(x) və g(x) funksiyaları olsun. Əgər x > k olarsa onda |f(x)| funksiyası  C*|g(x)| funksiyasıdan kiçik olacaq. c və k x-dən asılı olmayan sabitlərdi. Hesablanma zamanı ən pis hal qüvvəti ən böyük olana görə hesablandığından sabitlər və daha aşağı qüvvətlər nəzərə alınmır.
Nümunə:

Best Case 
Algoritmin ən yaxşı halda nə qədər icra olunacaqağını müəyyən etmək üçün istifadə olunur. Yuxardakı nümunədə kiçik bir dəyişiklik edərək ən yaxşı halı tapaq. N elementdən ibarət sırasız massivdə, hər hansı bir dəyərin axtarılması zamanı, həmin dəyərin massivin birinci indeksində yerləşən dəyəri olmasının omeqası, yəni, ən yaxşı hal Ω(1) olcaq.


Average Case 
Orta hal isə bütün mümkün hallar test edildikdən sonra hesablanır. Bu proses çox çətin və bəzən imkansız olduğundan  adətən ən pis hala (Big-O) bərabər götürülür. Yuxarıdakı massiv nümunəmizi götürsək bu halda hər elementin tapılma ehtimalı eyni olduğundan orta hal Θ(n/2) olacaq.