Teoria complexităţii

De la Wikipedia, enciclopedia liberă

(Redirecţionat de la Complexitatea algoritmilor)
Salt la: Navigare, căutare

Teoria complexităţii este o ramură a informaticii 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[1], 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 2n + n5 + 8 unităţi de timp, atunci complexitatea lui în timp este \mathcal{O}(2^n).

Ordinul de mărime \mathcal{O}(g) se defineşte în felul următor:

\mathcal{O}(g)= \left \{ f:\mathbb{N} \rightarrow \mathbb{R}_+| \left ( \exists c \in \mathbb{R}_{+}^{*}\right )\left ( \exists n_0 \in \mathbb{N}\right )\left ( \forall n \ge n_0\right )\left ( f(n) \le cg(n)\right ) \right \} [2]

unde g este o funcţie definită pe \mathbb{N} cu valori în \mathbb{R}. Se notează

f(n) = \mathcal{O}(g(n))

prin care se înţelege că funcţia f aparţine mulţimii \mathcal{O}(g(n)). Se spune că f este de ordinul al \mathcal{O} lui g, însemnând că f nu creşte mai repede, din punct de vedere asimptotic, decât g, eventual multiplicată printr-o constantă.


[modifică] Note

  1. ^ Schneier, p. 199
  2. ^ Ferucio Laurenţiu Ţiplea (2006). Fundamentele algebrice ale informaticii. Polirom. ISBN 973-46-0398-1.

[modifică] Bibliografie

  • Bruce Schneier (1996). Applied Cryptography, Second Edition: Protocols, Algorithms, and Source Code in C. Wiley Computer Publishing, John Wiley & Sons, Inc.. ISBN 0471128457.
 Acest articol din domeniul informaticii este deocamdată un ciot. Puteţi ajuta Wikipedia prin dezvoltarea lui.

Adus de la http://ro.wikipedia.org/wiki/Teoria_complexit%C4%83%C5%A3ii
Unelte personale