Introducere-Algoritmică

Acest tutorial introductiv cuprinde:

1. Câteva cuvinte despre algoritmi
2. Timpul de execuție
3. Cazul cel mai defavorabil și cazul mediu
4. Ordinul de complexitate

1. Despre algoritmi

Ce înseamnă de fapt cuvântul "algoritm"?

DEX wrote:ALGORÍTM, algoritme, s.n. Ansamblu de simboluri folosite în matematică și în logică, permițând găsirea în mod mecanic ( prin calcul ) a unor rezultate. ♦ P. gener. Succesiune de operații necesare în rezolvarea unei probleme oarecare.

Așa cum scrie și în DEX, un algoritm este o succesiune de pași pentru a ajunge la un rezultat final, a transforma ceva pentru a ajunge la rezultatul dorit. Dacă reușim să rezolvăm o problemă grea este foarte bine. Pașii pe care i-am folosit pentru a ajunge la rezultatul final se numește algoritm.

În programele noastre vom folosi algoritmi pentru a interpreta niște date de intrare și a returna un rezultat. Algoritmica urmărește performanța și folosirea resurselor. Noi ne vom referi în special la performanță.

Ce ar putea fi mai important decât perfomanța?

• User friendliness
• Stabilitate
• Securitate
• Functionalitate
• Simplitate
• Resurse omenești
• Timpul necesar scrierii codului

Dacă lucrurile aceste ar putea fi mai importante, atunci de ce ne mai ocupăm de performanță?
Putem face un exercițiu de abstractizare ( exercițiu inspirat dintr-o lecție de-a lui Charles E. Leiserson la MIT ).
Dacă ne imaginăm că performanță înseamnă bani, atunci ce am putea face cu 1 milion de euro ? Am putea să ne cumpărăm o casă,să o renovăm ( să o facem mai frumoasă ) să ne luăm o mașină ( să putem să ne mișcăm mai rapid ).
Deci noi cu performanța plătim ca să avem user friendliness ,funcționalitate,securitate etc.

Ne-am stabilit țelul, așa că trecem mai departe la timpul de execuție al unui algoritm.

2. Timpul de execuție

Durata de execuție a unui program depinde de dimensiunea și de caracteristicile datelor de intrare. Putem spune că un șir de 10000 de numere va fi sortat mai încet decât unul de 1000 de numere. De obicei timpul de execuție al unui algoritm crește dacă numărul datelor de intrare crește. Deci ar fi normal să descriem timpul de execuție ca o funcție de această variabilă.

Dimensiunea datelor de intrare depinde de problema care o rezolvăm. De exemplu, dacă trebuie să sortăm un șir de n numere atunci dimensiunea datelor de intrare va fi n. Astfel putem să ne gândim că avem un număr de n obiecte iar acesta va fi dimensiunea datelor de intrare. Totuși există cazuri când numărarea "obiectelor" ca date de intrare nu este o abordare bună. Dacă avem un graf, dimensiunea datelor de intrare se va calcula în funcție de câte vârfuri și câte noduri are graful respectiv.

Când ne gândim la timp ne gândim automat la secunde ( sau ceva asemănător ). Dacă algoritmul nostru este rulat pe calculatoare diferite desigur ca vom avea timpi de rulare diferiți. Un algoritm oarecare pe un Pentium I va rula mai încet decât pe un Pentium II. Dacă avem un computer a cărui procesor are o frecvață de 1Ghz și alt computer cu procesor de 2Ghz nu înseamnă că pe al doilea computer va rula de două ori mai rapid. Chiar și pe sisteme identice pot apărea diferențe. Sau poate diferă doar sistemul de operare. Sunt foarte mulți factori care modifică timpul ( în secunde ) de rulare a algoritmilor.

Astfel trebuie să regândim strategia și să încercăm să măsurăm timpul în funcție de numrărul pașilor elementari care sunt executați în algoritm. Putem aproxima că o linie de cod este executată în același timp de fiecare dată. Dar pot apărea și linii în care sunt apelate funcții și proceduri ale căror timp de execuție poate să fie diferit ( de exemplu,timpul de execuție a funcții care verifică existența unui elementr într-un șir de numere paote varia în funcție de lungimea șirului si de aranjamentul elementelor din șir ).

Dacă presupunem că se fac n pasi pentru a citi din fișier datele de intrare putem considera o funcție de forma T(n)=n2. Presupunem că algoritmul face n pași iar pentru afișare se vor folosi 2*n pași. Funcția noastră devine T(n)=n2+3n.

3. Cazul cel mai defavorabil și cazul mediu

Timpul de execuție al unui algoritm nu depinde doar de dimensiunea datelor de intrare. Acest timp depinde și de felul în care sunt organizate datele. De exemplu, dacă trebuie să sortăm un șir de numere “aproape sortat” vom avea nevoie de mai putin timp decât pentru un șir “sortat în ordine inversă”.

Astfel apare cazul mediu și cazul cel mai defavorabil ( desigur , există și cazul cel mai favorabil dar nu asta urmărim ). Cazul mediu de execuție este o medie a tuturor timpilor posibili înregistrati în cazul unor date de intrare de dimensiune dată. Timpul de executie pentru cazul cel mai defavorabil reprezintă timpul cel mai mare înregistrat în cazul unor date de intrare de dimensiune dată.

De obicei se folosește cazul cel mai defavorabil astfel încât să avem un punct de reper bun. Degeaba zicem că programul nostru rulează în minim 3 secunde. El poate să ruleze și un an în anumite cazuri defavorabile. Ideal ar fi să precizăm limita superioară ( de exemplu: programul rulează în maxim 6 secunde ). Astfel știm că pentru cazul cel mai defavorabil este nevoie de 6 secunde. Este un lucru bun să știm timpul de execuție pentru cazul cel mai defavorabil pentru că avem garanția că programul nostru nu va depăși niciodată acest timp.

4. Ordinul de complexitate

Pentru timpii de execuție se pot forma funcții foarte complicate dar noi nu avem nevoie de funcții complicate. Astfel a fost introdus ordinul de complexitate al unui algoritm. Acesta reprezintă o caracterizare a functiei respective, o descriere a ordinului de mărime. Ordinul de complexitate va indica doar ordinul de mărime al funcției iar restul termenilor care nu sunt importanți vor fi eliminați.

Dacă avem : ordinul de complexitate va fi :
Observăm că acum notăm ordinul de complexitate cu "O" și am ales termenul cu "puterea cea mai mare". După cum am spus , termenii neimportanți vor fi eliminați.A rămas doar termenul cu puterea cea mai are pentru că este cel mai important.
Dacă facem o incursiune în matematică vom observa că atunci când n->infinit n2 crește cel mai repede față de ceilalți termeni.

Ca să nu fie probleme , voi prezenta un tabel în care putem vedea care termeni este mai importanți decât ceilalți:


Dar de ce nu am scris și logan domină pe logbn dacă a>b? Nu este cazul. Toți termenii logaritmici sunt la fel de importanți. Vom demonstra acest lucru printr-un calcul matematic. Vom folosi formula de schimbare a bazei logaritmului ( din bază a în bază b ):



În cazul de față, C este o constantă dar după cum am văzut T(n)= 2*n2+5*n+3 se reduce la O(n2) pentru că constantele și unii termeni sunt ignorați. Astfel îl putem ignora pe C din expresia noastră - deci o funcție logaritmică nu poate domina altă funcție logaritmică. Astfel, pentru descrierea ordinului de complexitate nici nu se mai scrie baza logaritmului notația fiind O(log n).


Este mult mai ușor să determinăm ordinul de complexitate al întregului algoritm deoarece se reduc semnificativ calculele necesare.

Să presupunem ca avem 2 funcții f(n) și g(n). Vom considera că f(n) domina tot timpul pe g(n).
Astfel vom avea următoarele relații:



Exemplu:
Presupunem că ordinul de complexitate al datelor de intrare este O(n) , ordinul de complexitate al operației de prelucare a datelor este O(n2) și ordinul de complexitate al operației de scriere a datelor de ieșire este O(n). În acest caz, ordinul de complexitate al algoritmului va fi :

Ca să explic puțin mai detaliat vom face următoarele:
aveam cele 3 funcții de mai sus

Se observă clar că g(n) le domină pe celelalte (f(n) și h(n)).

În celelalte tutoriale vom studia mai mulți algoritmi analizându-le complexitatea.