Clasă de complexitate
În teoria complexității, o clasă de complexitate cuprinde problemele cu complexități similare, unde complexitatea măsoară cantitatea unei anumite resurse, de exemplu timp sau spațiu de memorie, necesară rezolvării problemei.
Clasa de complexitate, în teoria complexității, este o mulțime a problemelor algoritmice „referitoare la complexitate, bazate pe resurse”.[1] În general, clasa de complexitate este definită în funcție de tipul problemei algoritmice, de modelul de calcul și de resursele limitate, cum sunt timpul sau memoria.
Exemple
[modificare | modificare sursă]Exemple de clase de complexitate sunt clasele P, NP sau PSPACE.
Note
[modificare | modificare sursă]- ^ David S. Johnson, „A Catalog of Complexity Classes”. Handbook of Theoretical Computer Science, pp.67-161, Elsevier, 1990