Alqoritmin analizi - Haqqinda Melumat

Alqoritmin analizi (ing. Analysis of algorithms) — bir alqoritmin effektivliyini və performansını qiymətləndirmək üçün istifadə olunan metodlardır. Bu analiz alqoritmin işləmə sürətini və resurs tələbatını (məsələn, yaddaş və vaxt sərfiyyatını) təhlil etməyə kömək edir. Əsas məqsəd, alqoritmin xüsusən böyük həcmli məlumatlar üçün nə dərəcədə effektiv olduğunu və hansı hallarda üstünlük təşkil etdiyini müəyyən etməkdir.

Əsas aspektləri

Zaman mürəkkəbliyi

Zaman mürəkkəbliyi (ing. Time Complexity) — alqoritmin həlli üçün tələb olunan vaxtın giriş məlumatlarının ölçüsündən asılı olaraq necə dəyişdiyini təhlil edir. Giriş ölçüsünün artması ilə alqoritmin işləmə müddəti də artar və bu artımı təsvir etmək üçün asimptotik notasiya (böyük "O" notasıyası) istifadə edilir.

Zaman mürəkkəbliyi dərəcələri:

O(1): Sabit vaxt — alqoritm girişin ölçüsündən asılı olmayaraq eyni vaxtda işləyir. Məsələn, bir siyahıdan elementin mövcudluğunu yoxlamaq.
O(n): Xətti vaxt — alqoritmin işləmə vaxtı giriş ölçüsünə mütənasibdir. Məsələn, bir siyahıda müəyyən bir elementi axtarmaq.
O(n²): Kvadrat vaxt — alqoritmin vaxtı giriş ölçüsünün kvadratına görə dəyişir. Məsələn, sadə sıralama (bubble sort) alqoritmi.
O(log n): Loqaritmik vaxt — alqoritmin vaxtı giriş ölçüsünün logaritminə görə dəyişir. İki hissəli axtarış (binary search) buna bir nümunədir.

Məkan mürəkkəbliyi

Məkan mürəkkəbliyi (ing. Space Complexity) — alqoritmin işlənməsi üçün tələb olunan yaddaş həcmini təsvir edir. Əsas məqsəd alqoritmin giriş ölçüsündən asılı olaraq nə qədər əlavə yaddaş tələb etdiyini müəyyən etməkdir.

Məkan mürəkkəbliyini analiz edərkən əsasən iki əsas yaddaş növü nəzərə alınır:

Daimi yaddaş: Alqoritmin giriş ölçüsündən asılı olmayaraq tələb olunan yaddaş (məsələn, sabit dəyər üçün dəyişənlər).
Dinamik yaddaş: Alqoritmin giriş ölçüsünə görə dəyişən yaddaş miqdarı (məsələn, əlavə massivlər və ya məlumat strukturları).

Ən pis hal, orta hal və ən yaxşı hal analizi

Alqoritmin giriş məlumatlarına əsasən müxtəlif hallar üçün effektivliyini təhlil etmək üçün bu üsullar istifadə olunur:

Ən pis hal analizi: Alqoritmin mümkün olan ən uzun müddətdə çalışdığı haldır. Bu analiz, alqoritmin resurs tələbatının yuxarı həddini müəyyən edir.
Orta hal analizi: Alqoritmin ortalama halda necə çalışdığını göstərir. Girişlər təsadüfi olduqda alqoritmin performansını təsvir edir.
Ən yaxşı hal analizi: Alqoritmin mümkün olan ən qısa müddətdə çalışdığı haldır. Bu hal, çox vaxt nəzərə alınmır, çünki alqoritmlərin ümumiyyətlə optimallaşdırılmasında əhəmiyyətli təsir yaratmır.

Asimptotik notasiya

Alqoritmlərin performansını qiymətləndirmək üçün asimptotik notasiya istifadə edilir:

O-Böyük Notasiya (ing. Big O Notation): Ən pis hal analizini təsvir edir və alqoritmin üst sərhədini göstərir.
Ω-Böyük Notasiya (ing. Big Omega Notation): Ən yaxşı hal analizini təsvir edir və alqoritmin alt sərhədini göstərir.
Θ-Böyük Notasiya (ing. Theta Notation): Alqoritmin ortalama performansını və hər iki tərəfdən məhdudlaşdırılmasını göstərir.

Alqoritmlərin effektivlik müqayisəsi

Alqoritmin analizi, müxtəlif alqoritmləri müqayisə edərkən onların performansını dəqiq qiymətləndirməyə imkan verir. Məsələn, sıralama alqoritmlərinin (ing. bubble sort, merge sort, quick sort) zaman mürəkkəbliyi müqayisə edilərək, giriş ölçüsünün böyüklüyünə görə ən uyğun olan alqoritm seçilə bilər.

Təcrübə və teoriyaya əsaslanan analiz

Teoriyaya əsaslanan analiz: Zaman və məkan mürəkkəbliyinin riyazi yollarla təhlilini ehtiva edir.
Təcrübəyə əsaslanan analiz: Alqoritmlərin real mühitdə təcrübədən keçirilərək performanslarının analiz edilməsi ilə aparılır.

Alqoritmin analizi proqram təminatı və alqoritm dizaynında mühüm rol oynayır və bu analizlə proqramın effektivliyi artırıla bilər.

İstinadlar

Juraj Hromkovič. . Springer. 2004. 177–178. ISBN 978-3-540-14015-3.
. 28 August 2016. 28 August 2016 tarixində arxivləşdirilib.
Cormen, Thomas H., redaktor (3rd). Cambridge, Mass: MIT Press. 2009. 44–52. ISBN 978-0-262-03384-8. OCLC .
Alfred V. Aho; John E. Hopcroft; Jeffrey D. Ullman. . Addison-Wesley Pub. Co. 1974. ISBN 9780201000290., section 1.3
, cstheory.stackexchange.com
Giorgio Ausiello. . Springer. 1999. 3–8. ISBN 978-3-540-65431-5.
. . SIAM. 1983. 3–7. ISBN 978-0-89871-187-5.
Wegener, Ingo, , Berlin, New York: , 2005, səh. 20, ISBN 978-3-540-21045-0
. The Art of Computer Programming. Addison-Wesley.
. (3rd). Reading, MA: Addison-Wesley Professional. 1998. ISBN 978-0-201-31452-6.
; . An Introduction to the Analysis of Algorithms (2nd). Addison-Wesley. 2013. ISBN 978-0-321-90575-8.
- Greene, Daniel A.; Mathematics for the Analysis of Algorithms (Second). Birkhäuser. 1982. ISBN 3-7643-3102-X.
; ; ; . Introduction to Algorithms. Chapter 1: Foundations (Second). Cambridge, MA: MIT Press and McGraw-Hill. 2001. 3–122. ISBN 0-262-03293-7.

Xarici keçidlər

Vikianbarda Alqoritmin analizi ilə əlaqəli mediafayllar var.

[Hromkovič2004-1] Juraj Hromkovič. . Springer. 2004. 177–178. ISBN 978-3-540-14015-3.

[2] . 28 August 2016. 28 August 2016 tarixində arxivləşdirilib.

[3] Cormen, Thomas H., redaktor (3rd). Cambridge, Mass: MIT Press. 2009. 44–52. ISBN 978-0-262-03384-8. OCLC .

[AhoHopcroft1974-4] Alfred V. Aho; John E. Hopcroft; Jeffrey D. Ullman. . Addison-Wesley Pub. Co. 1974. ISBN 9780201000290., section 1.3

[5] , cstheory.stackexchange.com

[Ausiello1999-6] Giorgio Ausiello. . Springer. 1999. 3–8. ISBN 978-3-540-65431-5.

[Tarjan1983-7] . . SIAM. 1983. 3–7. ISBN 978-0-89871-187-5.

[Wegener20-8] Wegener, Ingo, , Berlin, New York: , 2005, səh. 20, ISBN 978-3-540-21045-0

[9] . The Art of Computer Programming. Addison-Wesley.

[10] . (3rd). Reading, MA: Addison-Wesley Professional. 1998. ISBN 978-0-201-31452-6.

[11] ; . An Introduction to the Analysis of Algorithms (2nd). Addison-Wesley. 2013. ISBN 978-0-321-90575-8.
Greene, Daniel A.; Mathematics for the Analysis of Algorithms (Second). Birkhäuser. 1982. ISBN 3-7643-3102-X.

[12] Greene, Daniel A.; Mathematics for the Analysis of Algorithms (Second). Birkhäuser. 1982. ISBN 3-7643-3102-X.

[12] ; ; ; . Introduction to Algorithms. Chapter 1: Foundations (Second). Cambridge, MA: MIT Press and McGraw-Hill. 2001. 3–122. ISBN 0-262-03293-7.