Kompleksiteten til en matematisk beregning er et mål på den nødvendige ressursbruken for å utføre beregningen. Dette er et vesentlig begrep for å vurdere hvor «god» en metode er, og blir først og fremst benyttet på beregningsmetoder (algoritmer) for datamaskin. Kompleksiteten uttrykkes som en funksjon av størrelsen på inngangsdataene til beregningen. Dersom beregningen f.eks. går ut på å multiplisere to tall, består inngangsdataene av disse to tallene, og størrelsen kan angis ved antall sifre i de to tallene.

Ressursene som er nødvendige for beregningen omfatter både tid- og romforbruk; tiden angis i antall nødvendige matematiske operasjoner, og romforbruket i nødvendig lagringskapasitet på datamaskinen.

For å vurdere en gitt beregningsmetode vil man vanligvis være interessert i å kjenne maksimal ressursbruk for metoden. Kompleksiteten angis da oftest ved en funksjon som beviselig alltid har større verdi enn den funksjonen som angir ressursbruken. Hvis man kan finne en slik begrensende funksjon som er en polynomfunksjon, sies beregningen å ha polynomisk kompleksitet. Se også kompleksitetsklasser.

Foreslå endringer i tekst

Foreslå bilder til artikkelen

Kommentarer

Har du spørsmål til artikkelen? Skriv her, så får du svar fra fagansvarlig eller redaktør.

Du må være logget inn for å kommentere.