In informatică algoritmul este un concept fundamental, deoarece
descrie procesul de calcul (de prelucrare a datelor).
Denumirea de algoritm provine de la numele matematicianului Abu Ja'far Mohammed ibn Mûsâ al-Khowârizmî, care a trăit in Persia și a scris în anul 825 îen (aproximativ), o carte care conținea reguli de aritmetică. |
Algoritmul trebuie sa aibă urmatoarele caracteristici:
a. Caracter discret. Fiecare acțiune prevăzută în
algoritm are un început și un sfârșit și durează un anumit interval
finit de timp, fiind numită și pas al algoritmului; Ținând cont de caracteristicile menționate, algoritmul poate fi definit și astfel: Algoritmul constă dintr-o mulțime ordonată de pași executabili, descriși fără echivoc, care definesc un proces finit. Algoritmul este, deci, descrierea riguroasă a unui proces. În schimb, nu orice proces poate fi descris printr-un algoritm. De exemplu, în cazul unei aplicații interactive bazată pe programarea orientată pe evenimente, executarea fiecărei metode în parte este un proces descris algoritmic (prin însăși metoda respectivă). Dacă însă urmărim executarea întregii aplicații, în care participă atât calculatorul, cât și sursele de evenimente externe (de exemplu operatorul uman care interacționează cu interfața grafică), constatăm ca acest proces nu este întotdeauna algoritmizabil. |
Pentru același algoritm, numărul de operații elementare depinde, în general, de cantitatea de date prelucrată. De exemplu, în algoritmii pentru efectuarea anumitor operații asupra tablourilor, numărul de operații poate să depindă de numărul de componente ale tabloului. Sa notăm cu n numărul de date de intrare prelucrate de algoritmul respectiv și cu f(n) funcția care exprimă relația dintre numărul de operații și numărul de date de intrare. Prezintă interes ce se întâmplă cu numărul de operații f(n) atunci când n crește. În figura de mai jos sunt trasate pe intervalul [1, 3] graficele unor funcții, pentru a pune în evidență tendința de variație a fiecăreia.
Se observă că, în ordinea vitezei de creștere, funcțiile pot fi ordonate astfel: log(n), n, n*log(n), n2, en. Daca funcția este polinomială în n, pentru valori mari ale lui n viteza de creștere a funcției depinde numai de cea mai mare putere a acestuia. Viteza de creștere a funcției exponențiale este, la valori mari ale variabilei n, mai mare decât a oricărei funcții polinomiale.
Complexitatea algoritmului se notează cu O(f(n)), unde f(n) este funcția care indică rapiditatea de creștere a numărului de operații elementare în raport cu numărul de date de intrare. Înmulțirea cu coeficient constant sau adunarea cu o constantă nu sunt luate în considerație, întrucât nu interesează valoarea exactă a funcției ci numai tendința de creștere. Din acest punct de vedere distingem, în ordinea vitezei de creștere:
Studiul complexității este una din problemele fundamentale ale algoritmicii. Mai există și alte categorii de complexitate, dar cele enunțate aici sunt suficiente pentru acest curs.