Teoria complexității

De la Wikipedia, enciclopedia liberă
Salt la: Navigare, căutare

Teoria complexității este o ramură a informaticii[1] care se ocupă cu studierea complexității algoritmilor. Complexitatea reprezintă puterea de calcul necesară implementării unui algoritm. Ea are două componente principale, și anume complexitatea în timp și cea în spațiu. Complexitatea în spațiu se referă la volumul de memorie necesar calculelor, iar cea în timp se referă la timpul necesar efectuării calculelor, ambele fiind exprimate ca funcții de n, unde n este mărimea datelor de intrare.

În general, complexitatea este exprimată folosind notația big O (), notație ce reține doar termenul care crește cel mai repede odată cu creșterea lui n[2], deoarece acest termen are impactul cel mai mare asupra timpului de execuție (sau al spațiului ocupat) al implementărilor algoritmului, ceilalți termeni devenind neglijabili pentru valori mari ale lui n. De exemplu, dacă un algoritm se execută în unități de timp, atunci complexitatea lui în timp este .

Ordinul de mărime se definește în felul următor:

[3]

unde este o funcție definită pe cu valori în .

Se notează

prin care se înțelege că funcția aparține mulțimii . Se spune că este de ordinul al lui , aceasta însemnând că nu crește mai repede, din punct de vedere asimptotic, decât , eventual multiplicată printr-o constantă.

Note[modificare | modificare sursă]

Bibliografie[modificare | modificare sursă]