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 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 \} [3]

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ă.

Note

  1. ^ Oded Goldreich. Complexity Theory - Material. Institutul de Ştiinţe Weizmann, Israel.
  2. ^ Schneier, p. 199
  3. ^ Ferucio Laurenţiu Ţiplea (2006). Fundamentele algebrice ale informaticii, Polirom. ISBN 973-46-0398-1.

Bibliografie

  • Schneier, Bruce (1996), Applied Cryptography, Second Edition: Protocols, Algorithms, and Source Code in C, Wiley Computer Publishing, John Wiley & Sons, Inc., ISBN 0471128457 
  • Weisstein, Eric W.. Complexity Theory. From MathWorld--A Wolfram Web Resource.
 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