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
En illustration som visar olika klasser av tidskomplexitet. Notera att är problemstorleken.

Referenser

Media som används på denna webbplats

Comparison computational complexity.svg
Författare/Upphovsman: Cmglee, Licens: CC BY-SA 4.0
Graphs of number of operations, N vs input size, n for common complexities, assuming a coefficient of 1