Tidskomplexitet

Från Wikipedia
Hoppa till navigering Hoppa till sök

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[redigera | redigera wikitext]