Kompleksitetsteori
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.
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.
O-notasjon rediger
Tidskompleksiteten til et problem er antall steg som må utføres for å løse en instans av problemet som funksjon av problemets størrelse (vanligvis målt i antall bit) ved bruk av den mest effektive algoritmen. For å få en intuitiv forståelse av dette, betrakt eksemplet med en instans som er n bit lang som kan løses med n² steg. I dette eksemplet vil vi si at problemet har tidskompleksitet n². Det eksakte antall steg vil naturligvis avhenge av hva slags maskin eller språk som blir brukt. For å unngå dette problemet bruker man vanligvis Stor O-notasjon. Dersom et problem har tidskompleksitet O(n²) på en typisk maskin, vil det også ha O(n²) på de fleste andre maskiner.
Å klippe gress har for eksempel lineær kompleksitet fordi det tar dobbelt så lang tid å klippe et dobbelt så stort areal. Å slå opp i en ordbok har derimot logaritmisk kompleksitet fordi en dobling av ordbokens størrelse bare krever ett ekstra oppslag (oppslag midt i ordboken vil redusere problemet til det halve).
Kompleksitetsklasser rediger
Utdypende artikkel: Kompleksitetsklasse
Man skiller gjerne på optimaliseringsproblemer og beslutningsproblemer. Et optimaliseringsproblem spør om det finnes en optimal verdi; et beslutningsproblem om det finnes en løsning, der svaret enten er ja eller nei. Disse problemene kan igjen kategoriseres i ulike kompleksitetsklasser, relatert etter hvor vanskelig det er å løse dem. Eksempler på kompleksitetsklasser er P, NP, NP-hardt.