Alqoritmik səmərəlilik

Alqoritmik səmərəlilik — bir alqoritmin mövcud resursları — xüsusilə vaxt və yaddaş — nə dərəcədə qənaətlə istifadə etdiyini göstərir.[1] Məqsəd, alqoritmi maksimum performansla, yəni daha az resurs sərf edərək, daha sürətli və effektiv işləməklə təmin etməkdir. Alqoritmik səmərəliliyin təmin edilməsi həm proqram təminatının daha yaxşı performans göstərməsi, həm də daha az hesablama gücü tələb etməsi üçün vacibdir.[2]

Əsas prinsiplər və metodlar

[redaktə | mənbəni redaktə et]

Zaman və məkan mürəkkəbliyinin təhlili

[redaktə | mənbəni redaktə et]
  • Zaman mürəkkəbliyi — bir alqoritmin çalışması üçün tələb olunan vaxtı təsvir edir. Səmərəli alqoritmlər mümkün qədər az vaxtda nəticə verir.
  • Məkan mürəkkəbliyi — isə alqoritmin yaddaş istifadəsini təsvir edir. Səmərəli alqoritmlər əlavə yaddaş tələbini minimuma endirir.

Bu iki göstərici balanslaşdırılaraq (vaxt-yaddaş ticarəti), həm sürətli, həm də yaddaş baxımından qənaətli alqoritmlər inkişaf etdirilə bilər.[3]

Asimptotik notasiyalarla analiz

[redaktə | mənbəni redaktə et]

Asimptotik notasiya (Big O, Omega, və Theta) alqoritmin giriş məlumatlarının həcmi artdıqca necə davranacağını təsvir edir. Məsələn, **O(n)** və ya **O(log n)** mürəkkəbliyə malik alqoritmlər **O(n²)** mürəkkəbliyə malik olanlardan daha səmərəlidir, çünki onlar daha sürətli işləyir və daha böyük giriş ölçülərinə daha uyğun gəlir.[4]

Daha sürətli alqoritm və məlumat strukturunun seçimi

[redaktə | mənbəni redaktə et]

Ənənəvi sıralama alqoritmi olan Bubble Sort (O(n²)) yerinə daha sürətli Merge Sort və ya Quick Sort (O(n log n)) istifadə etmək, alqoritmik səmərəliliyi artırır. Məlumat strukturları da səmərəliliyə böyük təsir göstərir. Məsələn, tez-tez məlumat axtarışı tələb edən bir tətbiq üçün Hash Table istifadə etmək daha səmərəli ola bilər, çünki axtarış O(1) mürəkkəbliyindədir.

Təkrarlanan hesablamaların azaldılması

[redaktə | mənbəni redaktə et]

Təkrarlanan hesablamaları aradan qaldırmaq üçün dinamik proqramlaşdırma texnikaları tətbiq edilir. Bu metodla müəyyən bir hesablamanın nəticəsi yadda saxlanır və lazım gəldikdə yenidən istifadə olunur. Bu yanaşma, məsələn, Fibonacci ədədlərinin hesablanmasında böyük vaxt qənaəti yaradır.[5]

Böl və hakim ol texnikası

[redaktə | mənbəni redaktə et]

Böl və hakim ol texnikası (ing. Divide and Conquer) — problemi kiçik alt problemlərə bölərək daha asan şəkildə həll etməyi nəzərdə tutur. Məsələn, Merge Sort və Binary Search bu prinsip əsasında qurulub və böyük giriş məlumatlarına tətbiq edilə bilən səmərəli alqoritmlərdir.Rekursiya, bəzən daha çox yaddaş və vaxt tələb edə bilər. Mümkün hallarda rekursiv funksiyaları iterativ (dövr) versiyalara çevirmək alqoritmik səmərəliliyi artırır. Tənbəl hesablama, yalnız ehtiyac olduqda hesablamanın aparılmasını təmin edir və beləliklə lazımsız hesablamaların qarşısını alır. Bu yanaşma böyük verilənlər toplusu ilə işləyərkən yaddaş və vaxt qənaəti üçün uyğundur.[6]

Pessimal analiz və ən pis hal təhlili

[redaktə | mənbəni redaktə et]
  • Alqoritmin ən pis halda necə çalışacağını nəzərə alaraq optimallaşdırmalar etmək səmərəliliyi artırır. Bu analiz, alqoritmin çoxlu sayda məlumat daxilində sabit performans göstərməsini təmin edir.
  • Paralel işləmə ilə böyük həcmli hesablamaları bir neçə nüvədə icra etməklə alqoritmin ümumi işləmə vaxtını azaltmaq mümkündür. Asinxron metodlarla da eyni anda bir neçə iş görmək alqoritmin səmərəliliyini artıra bilər.[7]

Alqoritmik səmərəliliyin tətbiqləri

[redaktə | mənbəni redaktə et]

Alqoritmik səmərəlilik, böyük həcmli verilənlərin işlənməsi, real vaxt tətbiqləri, qlobal axtarış motorları və maşın öyrənmə sahələrində çox əhəmiyyətlidir. Daha səmərəli alqoritmlər, həll müddətini qısaldır, yaddaş istifadəsini azaldır və sistemlərin ümumi performansını artırır.[8]

Səmərəli alqoritmlər yaratmaq, həm riyazi düşüncə, həm də resurs tələbatının dəqiq təhlilini tələb edir. Bu optimallaşdırma ilə proqram təminatı daha sürətli və resurs baxımından qənaətli olur, beləliklə istifadəçilər daha yaxşı performans əldə edir.

İstinadlar

[redaktə | mənbəni redaktə et]
  1. ↑ David A. Grossman, Ophir Frieder, Information Retrieval: Algorithms and Heuristics, 2nd edition, 2004, ISBN 1402030045
  2. ↑ Knuth, Donald, "Structured Programming with go-to Statements" (PDF), Computing Surveys, 6 (4), 1974: 261–301, CiteSeerX 10.1.1.103.6084, doi:10.1145/356635.356640, 24 August 2009 tarixində orijinalından (PDF) arxivləşdirilib, İstifadə tarixi: 19 May 2013
  3. ↑ Green, Christopher, Classics in the History of Psychology, 27 September 2013 tarixində arxivləşdirilib, İstifadə tarixi: 19 May 2013
  4. ↑ Kriegel, Hans-Peter; Schubert, Erich; Zimek, Arthur. "The (black) art of runtime evaluation: Are we comparing algorithms or implementations?". Knowledge and Information Systems. 52 (2). 2016: 341–378. doi:10.1007/s10115-016-1004-2. ISSN 0219-1377.
  5. ↑ OSNews Staff. "Nine Language Performance Round-up: Benchmarking Math & File I/O". osnews.com. 2019-11-28 tarixində arxivləşdirilib. İstifadə tarixi: 2018-09-18.
  6. ↑ "Definition of ALGORITHM". Merriam-Webster Online Dictionary (ingilis). February 14, 2020 tarixində arxivləşdirilib. İstifadə tarixi: 2019-11-14.
  7. ↑ "Floating Point Benchmark: Comparing Languages (Fourmilog: None Dare Call It Reason)". Fourmilab.ch. 4 August 2005. 11 December 2011 tarixində arxivləşdirilib. İstifadə tarixi: 14 December 2011.
  8. ↑ Guy Lewis Steele, Jr. "Debunking the 'Expensive Procedure Call' Myth, or, Procedure Call Implementations Considered Harmful, or, Lambda: The Ultimate GOTO". MIT AI Lab. AI Lab Memo AIM-443. October 1977.[1] Arxiv surəti 26 sentyabr 2024 tarixindən Wayback Machine saytında