Tidskompleksitet

Tidskompleksitet er inden for datalogien et udtryk for, hvordan tidsforbruget i en algoritme stiger, når mændgen af inddata øges.

Med udgangspunkt i en formel for tidsforbruget finder man det led, der udføres oftest og dette led bruges som udgangspunkt for beregningen af 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

Da det ikke er praktisk at lave en præcis analyse/beregning af tidsforbruget, benytter man ofte forskellige afrundinger. En af de mest populære afrundinger, er O-notationen (store o), der er en overslags-beregning af det værste tilfælde af inddata. Der findes også en lidt mere detaljeret variant, kaldet Amortiseret analyse, der forsøger at fortælle hvordan tidsforbruget er i de fleste normale tilfælde. En tredje interessant analyse er beregningen af det bedste tilfælde (lille o) o-notationen, så man dermed har øvre og nedre grænse for forventede køretid af forskellige algoritmer.

I udskriftseksemplet, kan vi nok antage at det er hurtigere at udskrive en tom linje, frem for en linje hvor samtlige punkter skal farvelægges. O(N) vil derfor være tidsforbruget for fuld farvelægning, mens o(N) - lille-o - er for en tom linje. A(N) (amortiseret), vil f.eks. antage en 10% farvelægning.

Nogle eksempler for hvordan O-notationen, og de andre, skrives og hvordan algoritmens tidsforbrug øges:

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(N²)	Kvadratisk tid. Tre gange så meget input giver ni gange så lang behandlingstid.
O(log₂ N)	Logaritmisk tid. Tidsforbruget stiger logaritmisk med mængden af input.