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 for eksempel 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.

Faktaboks

Uttale
kompleksitˈet

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. Slike problemer hører til kompleksitetsklassen P.

Les mer i Store norske leksikon

Kommentarer

Kommentarer til artikkelen blir synlig for alle. Ikke skriv inn sensitive opplysninger, for eksempel helseopplysninger. Fagansvarlig eller redaktør svarer når de kan. Det kan ta tid før du får svar.

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

eller registrer deg