Tidskomplexitet

Inom datavetenskapen är tidskomplexitet beräkningskomplexiteten för en algoritm mätt i tid.

Tidskomplexitet beräknas genom att man estimerar tidskostnaden för de elementära operationer som krävs i en algoritm. Vanligtvis beror antalet steg på hur stort problemstorleken är, det vill säga indatastorlek, varför man uttrycker tidskomplexitet som en funktion av problemstorleken.

Ofta är olika typer av probleminstanser svårare eller lättare för en algoritm. Om så är fallet kan man gör en bästa fallet-analys, en värsta fallet-analys eller en genomsnittsanalys.

En illustration som visar olika klasser av tidskomplexitet. Notera att $n$ är problemstorleken.

Referenser

• Janlert, Wiberg, Lars-Erik, Torbjörn (2000). Datatyper och algoritmer 
• Sipser, Michael. (2006). Introduction to the theory of computation (2nd, International ed). Thomson Course Technology. ISBN 0619217642. OCLC 64006340. https://www.worldcat.org/oclc/64006340. Läst 13 juni 2019