Računski resurs

Izvor: Wikipedija
Skoči na: orijentacija, traži

U računskoj teoriji složenosti, računski resurs je resurs korišten od strane nekog računskog modela prilikom rješavanja računskog problema. Najjednostavniji računski resursi su vrijeme računanja, broj koraka potrebnih za rješenje problema, te memorijski prostor, količina spremnika potrebnog za rješavanje problema, iako su mnogo složeniji resursi identificirani.

Računski je problem općenito definiran djelovanjem akcija na validan ulaz - primjeri problema mogu biti "za dani cijeli broj n, odredi je li n prost broj", ili "za dane brojeve x i y, izračunaj umnožak x*y". Kako ulazi rastu, količina računskih resursa potrebnih ra rješavanje problema će rasti. Stoga su resursi potrebni za rješavanje problema opisani asimptotskom analizom, identificiranjem resursa kao funkcije duljine ili veličine ulaza.

Računski su resursi korisni jer možemo proučavati koji problemi mogu biti izračunati u određenim količinama svakog računskog resursa. Na taj se način može odrediti je li algoritam rješavanja problema optimalan. Skup svih računskih problema koji mogu biti riješeni korištenjem određene količine određenog računskog resursa jest klasa složenosti, i odnosi između različitih klasa složenosti su jedna od najvažnijih tema u teoriji složenosti.