Teoria complexității

• Pentru alte sensuri, utilizați pagina Teoria complexității (dezambiguizare)
  

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 (${\mathcal {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\geq n_{0}\right)\left(f(n)\leq 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 ${\mathcal {O}}$ al lui $g$, aceasta însemnând că $f$ nu crește mai repede, din punct de vedere asimptotic, decât $g$, eventual multiplicată printr-o constantă.

Vezi și

• Complexitate
• Teoria complexității (dezambiguizare)

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.