Tidskompleksitet

Fra Wikipedia, den frie encyklopædi
Gå til: navigation, søg
Scientist.svg Svært stof
Denne artikel omhandler svært stof. Der er endnu ikke taget hensyn til ikke-eksperter. Du kan hjælpe ved at skrive en letforståelig indledning.

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.

Kompleksitetsklasserne[redigér | redigér wikikode]

Der eksisterer forskellige klasser for algoritmers tidskompleksitet. Hovedeklasserne er:

Programmering Stub
Denne artikel om datalogi eller et datalogi-relateret emne er kun påbegyndt. Hvis du ved mere om emnet, kan du hjælpe Wikipedia ved at udvide den.