Tidskompleksitet

Fra Wikipedia, den frie encyklopædi

Tidskompleksitet er inden for datalogien et udtryk for, hvor lang tid en operation tager når mængden af input bliver meget stor.

Med udgangspunkt i en formel for tidsforbruget finder man det led, der vokser hurtigst og dette led betegnes som tidskompleksiteten.

Et simpelt eksempel er udskrivning af tekst på en printer. Der bruges tid på tre ting: Start på udskrift, udskrift af de enkelte linjer og færdiggørelse, hvor det sidste papir skubbes ud. Start og stop må være uafhængig af dokumentets størrelse, mens tiden for selve udskriften stiger med mængden af input. Alt i alt bliver tidsforbruget:

Tid = N * sidetid + start/stoptid

Tidsforbruget vokser lineært med N, hvilket noteres O(N). Det er kun det led, der vokser mest, som nævnes.

Almindelige tidskompleksiteter

Tidskompleksitet	Beskrivelse
O(1)	Konstant tid. Oprationens varighed er uafhængig af mængden af input.
O(N)	Tiden for operationen vokser lineært med mængden af input.
O(N2)	Kvadratisk tid. Tre gange så meget input giver ni gange så lang behandlingstid.
O(log2 N)	Logaritmisk tid. Tidsforbruget stiger logaritmisk med mængden af input.

Denne artikel er kun påbegyndt. Hvis du ved mere om emnet, kan du hjælpe Wikipedia ved at udvide den. Du kan også give den en bedre beskrivelse.