Tidskompleksitet

Tidskompleksitet er inden for datalogien et udtryk for, hvordan tidsforbruget i en algoritme stiger, når størrelsen af input øges.

Tiden det tager at eksekvere et program afhænger både af programmet, input og computeren der bruges. For at undgå afhængigheden af computeren tæller man ofte antallet af simple operationer der udføres.^[1] Eksempler på simple operationer kan være plus, gange eller sammenligning af tal.

Hvis der er flere input af samme størrelse, hvor algoritmen udfører et forskelligt antal operationer, angives det værste tilfælde ofte.^[2] Antallet af operationer angives ofte som en funktion af størrelsen af inputtet. O-notation anvendes ofte ved angivelse af tidskompleksitet, da funktionerne man arbejder med ofte, er komplekse.

I en analyse af en algoritme bruges ofte pessimistiske antagelser om køretiden. En analyse af tidskompleksiteten af en printer kunne f.eks. bygge på, at printeren skal have nyt blæk før udskrivning af hver enkelt side. Dette kan give dårlige og misvisende resultater. For at imødegå dette problem kan en amortiseret analyse bruges.^[3] I en amortiseret analyse, vil man udregne hvor ofte den dyre operation, her at skifte blæk, udføres og fordele omkostningen på de enkelte operationer. Hvis det at skifte blæk tager 20 operationer og gøres ved hver tiende udskrift vil det amortiseret koste to operationer per udskrift. Det er vigtigt at huske, at der stadig er tale om en analyse af det værste tilfælde.

O-notation

O-notation bruges til at beskrive, hvordan funktioner opfører sig, når input går mod uendeligt. Intuitivt kan det forstås som en form for afrunding, hvor man beskriver udviklingen af en funktion for tilstrækkeligt store input. O-notation bruges ofte i datalogi til at beskrive tidskompleksiteten af algoritmer.^[4]

Som eksempel kan funktionen $f(n)=5n^{2}$ bruges. I O-notation vil man beskrive den som $O(n^{2})$ . Dette betyder at der findes en konstant således at $f(n)=c\cdot n^{2}$ vokser hurtigere end $f$ . Siden vi beskriver øvre grænser er $f$ også $O(n^{3})$ , $O(2^{n})$ og så videre. Den mindste funktion angives dog ofte, da dette er mere præcist. Funktionen er dog ikke $O(n)$ , da $f$ altid blive større end $c\cdot n$ , når $n$ bliver stor nok.

Udover store O-notation som beskrevet her findes også $\Omega$ -notation.^[5] Her er man interesseret i nedre grænser. Funktionen $f(n)=5n^{2}$ er således $\Omega (n^{2})$ , $\Omega (n)$ , $\Omega (1)$ og så videre da $f$ udvikler sig hurtigere end dem. $f$ er dog ikke $\Omega (n^{3})$ , da der ikke eksisterer et $c$ således at $f$ stiger langsommere end $c\cdot n^{3}$ .

Endeligt findes der også o- og $\omega$ -notation.^[6] Mens store O-notation og $\Omega$ -notation kan ses som bløde uligheder er der her tale om skarpe uligheder. Funktionen $f=5n^{2}$ er således $O(n^{2})$ , men ikke $o(n^{2})$ . Den er dog stadig $o(n^{3})$ . Formelt er kravet at for alle $c$ vil $c\cdot n^{3}$ vokse hurtigere end $f$ , når $n$ , bliver stor nok. $\omega$ -notation er på samme måde en skarp ulighed for $\Omega$ -notation.

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(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.
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.

Referencer

↑ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009), "2", Introduction To Algorithms (3rd udgave), Cambridge, MA: The MIT Press, s. 25, ISBN 978-0-262-03384-8
↑ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009), "2", Introduction To Algorithms (3rd udgave), Cambridge, MA: The MIT Press, s. 27, ISBN 978-0-262-03384-8
↑ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009), "17", Introduction To Algorithms (3rd udgave), Cambridge, MA: The MIT Press, s. 451, ISBN 978-0-262-03384-8
↑ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009), "3", Introduction To Algorithms (3rd udgave), Cambridge, MA: The MIT Press, s. 43, ISBN 978-0-262-03384-8
↑ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009), "3", Introduction To Algorithms (3rd udgave), Cambridge, MA: The MIT Press, s. 48, ISBN 978-0-262-03384-8
↑ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009), "3", Introduction To Algorithms (3rd udgave), Cambridge, MA: The MIT Press, s. 50, ISBN 978-0-262-03384-8

[1] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009), "2", Introduction To Algorithms (3rd udgave), Cambridge, MA: The MIT Press, s. 25, ISBN 978-0-262-03384-8

[2] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009), "2", Introduction To Algorithms (3rd udgave), Cambridge, MA: The MIT Press, s. 27, ISBN 978-0-262-03384-8

[3] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009), "17", Introduction To Algorithms (3rd udgave), Cambridge, MA: The MIT Press, s. 451, ISBN 978-0-262-03384-8

[4] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009), "3", Introduction To Algorithms (3rd udgave), Cambridge, MA: The MIT Press, s. 43, ISBN 978-0-262-03384-8

[5] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009), "3", Introduction To Algorithms (3rd udgave), Cambridge, MA: The MIT Press, s. 48, ISBN 978-0-262-03384-8

[6] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009), "3", Introduction To Algorithms (3rd udgave), Cambridge, MA: The MIT Press, s. 50, ISBN 978-0-262-03384-8

[1]

[2]

[3]

[4]

[5]

[6]