Tidskompleksitet

Innenfor informatikken er tidskompleksiteten til en algoritme en kvantifisering av det tidsrom som tar å kjøre algoritmen som en funksjon av lengden på strengen som representerer innmating. Tidskompleksiteten til en algorime er vanligvis uttrykt gjennom stor O-notasjonen 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  for enhver n (større enn n0), er den asymptotiske tidskompleksiteten lik O(n3).

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 tid
 Faktoriell tid
 Dobbel-eksponentiell tid

 Se også 
 NP-komplett

Kategori:Algoritmer