Teoria complexității

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, 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 $2^n+n^5+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 \}$

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

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. http://mathworld.wolfram.com/ComplexityTheory.html.