Tidskomplexitet

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

Tidskomplexitet är inom datavetenskapen ett mått för hur lång körtid en algoritm kräver. Tidskomplexiteten uppmäts genom att räkna ut hur många beräkningssteg som krävs i förhållande till storleken på indata. I den vanliga beräkningsmodellen för att uppmäta tidskomplexitet används en grundläggande operation som kostar en tidsenhet. Det vill säga, den minsta beståndsdelen i en algoritm är en operation såsom addition. För de flesta algoritmer beror körtiden på hur indata ser ut, t.ex. om vi ska sortera något som nästan redan är sorterat går det åt lite tid. Däremot med indata som är väldigt bra blandat tar det längre tid än om det nästan är sorterat. Då kan en värsta-fallet-analys vara aktuell, det vill säga den längsta körtid som kan tänkas uppstå.

Referenser[redigera | redigera wikitext]

  • Janlert, Wiberg, Lars-Erik, Torbjörn (2000). Datatyper och algoritmer