Kompleksitetsteori
From Wikipedia, the free encyclopedia
Kompleksitetsteori er den delen av informatikken som omhandler ressursene som trengs for å løse et bestemt problem. De vanligste ressursene er tid (hvor mange operasjoner som må utføres for å løse problemet) og plass (hvor mye minne som trengs for å løse et problem). Andre typer ressurser kan også analyseres, f.eks. hvor mange parallelle prosessorer som trengs for å løse et parallelt problem. Kompleksitetsteori skiller seg fra beregnbarhetsteori, som omhandler hvorvidt et gitt problem i det hele tatt kan løses, uavhengig av ressursene som kreves.
Kildeløs: Denne artikkelen mangler kildehenvisninger, og opplysningene i den kan dermed være vanskelige å verifisere. Kildeløst materiale kan bli fjernet. Helt uten kilder. (10. okt. 2015) |
Et enkelt «problem» er en fullstendig mengde av relaterte spørsmål, der hvert spørsmål er en streng av endelig lengde. For eksempel, er problemet FAKTORISER: «Gitt et heltall skrevet på binær form, finn alle primtallsfaktorene til det tallet.» Et bestemt spørsmål kalles en instans av problemet. For eksempel er «Finn alle primtallsfaktorene til tallet 15» en instans av problemet FAKTORISER.