Alqoritmin analizi

Alqoritmin analizi (ing. Analysis of algorithms) — bir alqoritmin effektivliyini və performansını qiymətləndirmək üçün istifadə olunan metodlardır.^[1] 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.^[2]

Ə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.^[3]

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.^[4]

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.^[5]

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ı).^[6]

Ə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.^[7]
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.^[8]

Asimptotik notasiya

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

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.^[10]

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

Teoriyaya əsaslanan analiz: Zaman və məkan mürəkkəbliyinin riyazi yollarla təhlilini ehtiva edir.^[11]
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.^[12]

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č. Theoretical computer science: introduction to Automata, computability, complexity, algorithmics, randomization, communication, and cryptography. Springer. 2004. 177–178. ISBN 978-3-540-14015-3.
↑ "Knuth: Recent News". 28 August 2016. 28 August 2016 tarixində orijinalından arxivləşdirilib.
↑ Cormen, Thomas H., redaktorIntroduction to algorithms (3rd). Cambridge, Mass: MIT Press. 2009. 44–52. ISBN 978-0-262-03384-8. OCLC 311310321.
↑ Alfred V. Aho; John E. Hopcroft; Jeffrey D. Ullman. The design and analysis of computer algorithms. Addison-Wesley Pub. Co. 1974. ISBN 9780201000290., section 1.3
↑ Examples of the price of abstraction?, cstheory.stackexchange.com
↑ Giorgio Ausiello. Complexity and approximation: combinatorial optimization problems and their approximability properties. Springer. 1999. 3–8. ISBN 978-3-540-65431-5.
↑ Robert Endre Tarjan. Data structures and network algorithms. SIAM. 1983. 3–7. ISBN 978-0-89871-187-5.
↑ Wegener, Ingo, Complexity theory: exploring the limits of efficient algorithms, Berlin, New York: Springer-Verlag, 2005, səh. 20, ISBN 978-3-540-21045-0
↑ Knuth, Donald. The Art of Computer Programming. Addison-Wesley.
↑ Sedgewick, Robert. Algorithms in C, Parts 1-4: Fundamentals, Data Structures, Sorting, Searching (3rd). Reading, MA: Addison-Wesley Professional. 1998. ISBN 978-0-201-31452-6.
↑
Sedgewick, Robert; Flajolet, Philippe. An Introduction to the Analysis of Algorithms (2nd). Addison-Wesley. 2013. ISBN 978-0-321-90575-8.
- Greene, Daniel A.; Knuth, Donald E. Mathematics for the Analysis of Algorithms (Second). Birkhäuser. 1982. ISBN 3-7643-3102-X.
↑ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford. 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č. Theoretical computer science: introduction to Automata, computability, complexity, algorithmics, randomization, communication, and cryptography. Springer. 2004. 177–178. ISBN 978-3-540-14015-3.

[2] "Knuth: Recent News". 28 August 2016. 28 August 2016 tarixində orijinalından arxivləşdirilib.

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

[AhoHopcroft1974-4] Alfred V. Aho; John E. Hopcroft; Jeffrey D. Ullman. The design and analysis of computer algorithms. Addison-Wesley Pub. Co. 1974. ISBN 9780201000290., section 1.3

[5] Examples of the price of abstraction?, cstheory.stackexchange.com

[Ausiello1999-6] Giorgio Ausiello. Complexity and approximation: combinatorial optimization problems and their approximability properties. Springer. 1999. 3–8. ISBN 978-3-540-65431-5.

[Tarjan1983-7] Robert Endre Tarjan. Data structures and network algorithms. SIAM. 1983. 3–7. ISBN 978-0-89871-187-5.

[Wegener20-8] Wegener, Ingo, Complexity theory: exploring the limits of efficient algorithms, Berlin, New York: Springer-Verlag, 2005, səh. 20, ISBN 978-3-540-21045-0

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

[10] Sedgewick, Robert. Algorithms in C, Parts 1-4: Fundamentals, Data Structures, Sorting, Searching (3rd). Reading, MA: Addison-Wesley Professional. 1998. ISBN 978-0-201-31452-6.

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

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

[12] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford. Introduction to Algorithms. Chapter 1: Foundations (Second). Cambridge, MA: MIT Press and McGraw-Hill. 2001. 3–122. ISBN 0-262-03293-7.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]