În algoritmică , complexitatea spațiului este o măsură a spațiului utilizat de un algoritm , în funcție de proprietățile intrărilor sale. Spațiul contează numărul maxim de sloturi de memorie utilizate simultan în timpul unui calcul. De exemplu, numărul de simboluri care trebuie păstrate pentru a putea continua calculul.
De obicei, spațiul care este luat în considerare atunci când se vorbește despre spațiul necesar pentru intrări având proprietăți date este cel mai mare spațiu necesar dintre aceste intrări; vorbim de complexitate spațială în cel mai rău caz. Studiile de complexitate se referă în majoritatea cazurilor la comportamentul asimptotic , atunci când magnitudinile intrărilor care influențează complexitatea spațială tind spre infinit, iar în prezent se folosește notațiile O mari ale lui Landau .
O altă măsură a complexității este complexitatea timpului .
Teoria complexității constă în gruparea problemelor algoritmice folosind resurse similare. Clasa de complexitate dSpace (f) , pentru o crestere functiei f , este clasa de probleme care pot fi rezolvate cu un spațiu O (f) într - un mod determinist. Spațiul aici este numărul de sloturi ale panglicii de lucru a mașinii Turing vizitate în timpul calculului. Pentru a vorbi despre SPACE (f), trebuie să adăugăm și condiția ca mașina să se oprească pe toate intrările.
Clasa NSPACE (f) corespunde DSPACE, dar pentru mașinile nedeterministe .
Clasele clasice de spațiu sunt L , NL , PSPACE și EXPSPACE . Teorema Savitch se conectează clase deterministe și non-deterministe.