Tidskompleksitet

Tidskompleksitet er inden for datalogien et udtryk for, hvordan tidsforbruget i en algoritme stiger, når mængden 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 + starttid + stoptid

(N er sidetallet) 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. Operationens 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.
O(2^N)	Eksponentiel tid. Tidforbruget stiger ekponentielt med mængden af input.

Kompleksitetsklasserne

Der eksisterer forskellige klasser for algoritmers tidskompleksitet. Hovedeklasserne er:

• P: En beslutningsproblems-algoritme, som kan udførers på polynomisk tid med en Turing-maskine.
• NP: En beslutningsproblems-algoritme, som kan udførers på polynomisk tid med en nondeterministisk Turing-maskine.
• ZPP: En beslutningsproblems-algoritme, som kan udførers uden fejl på polynomisk tid med en probabilistisk Turing-maskine (f.eks. en kvantecomputer).

Spire Denne artikel om datalogi eller et datalogi-relateret emne er en spire som bør udbygges. Du er velkommen til at hjælpe Wikipedia ved at udvide den.