Redigerer Tidskompleksitet

Innenfor [[informatikk]]en er '''tidskompleksiteten''' til en [[algoritme]] en kvantifisering av det tidsrom som tar å kjøre algoritmen som en funksjon av lengden på [[streng (informatikk)|strengen]] som representerer innmating. Tidskompleksiteten til en algorime er vanligvis uttrykt gjennom [[stor O-notasjon]]en uten koeffisienter og lavere ordens begreper. Uttrykt på denne måten er den beskrevet som en [[asymptote]], ettersom innmatingens størrelse går mot uendelig. For eksempel, hvis tiden det tar for en algoritme på alle innmatinger av størrelse ''n'' er {{nowrap|1=5''n''<sup>3</sup> + 3''n''}} for enhver ''n'' (større enn ''n<sub>0</sub>''), er den asymptotiske tidskompleksiteten lik O(''n''<sup>3</sup>).

Noen eksempler på tidskompleksitet er:
* Konstant tid
* Logaritmisk tid
* Polylogaritmisk tid
* Sub-lineær tid
* Lineær tid
* Kvasilineær tid
* Sub-kvadratisk tid
* Polynomisk tid
* Superpolynomisk tid
* Kvasi-polynomisk tid
* Subeksponentiell tid
* [[Eksponentiell vekst|Eksponentiell tid]]
* Faktoriell tid
* Dobbel-eksponentiell tid

== Se også ==
* [[NP-komplett]]

{{stubb}}

{{Autoritetsdata}}

[[Kategori:Algoritmer]]