tidskompleksiteten

Tidskomplexiteten avser hur lång tid en datorberäkning förväntas ta i förhållande till storleken på indata. Den fokuserar på antalet grundoperationer eller steg som krävs när indata växer och används ofta som teoretiskt mått på algoritmers effektivitet. Inom datorvetenskapen används asymptotisk analys och notationssystemet Big-O, Big-Theta och Big-Omega för att beskriva tillväxttakt oberoende av maskinvara och konstanter.

Big-O anger en övre gräns på tillväxten, Theta ger en exakt asymptotisk gräns, och Omega anger en nedre gräns. Man skiljer också mellan olika scenarier: worst-case, best-case och average-case.

Vanliga tidsklasser inkluderar O(1) konstant tid, O(log n) sublinear, O(n) linjär, O(n log n) linjär-logaritmisk, O(n^2) kvadratisk, samt O(2^n) och O(n!) i exponentiella klasser. Exempel: binärsökning har O(log n) tid, linjär sökning O(n), mergesort och heapsort ungefär O(n log n), medan bubbelort ofta är O(n^2).

Analysmetoder: man identifierar antalet loopiterationer och rekursioner. För rekursion används ofta återkopplingsrelationer och transform med Master Theorem.

Viktigt att notera: tidskomplexitet är teoretiskt och bortser från konstanter och maskinberoende faktorer som minnesåtgång, cache och parallellisering. Därför används det som vägledning när man jämför algoritmer eller prioriterar förbättringar, inte som exakt tidsuppskattning.