Tidskomplexitet

Tidskomplexitet är ett mått på hur antalet grundläggande operationer som en algoritm utför växer med storleken på indata, n. Den används för att jämföra algoritmer och för att förutsäga hur programmet presterar när indata växer. Tidskomplexitet beskriver tillväxttakten, medan faktiska körningstider påverkas av hårdvara och implementation.

Analys görs ofta med asymptotisk notation: Big O anger en övre gräns, Big Theta ger en ungefärlig exakt tillväxt, och Big Omega anger en nedre gräns. Ofta redovisas värsta fallet, bästa fallet och genomsnittsfallet. Vanliga klasser är O(1), O(log n), O(n), O(n log n), O(n^2), O(2^n) och O(n!).

Exempel: Att söka i en osorterad lista kräver i värsta fall n jämförelser, dvs O(n). Att hitta ett element i en sorterad lista med binär sökning kräver O(log n) jämförelser. Sorteringsalgoritmer varierar: mergesort och heapsort har O(n log n) i de flesta fall, medan quicksort i genomsnitt är O(n log n) men kan ha O(n^2) i dåliga fall.

Eftersom tidskomplexiteten beskriver tillväxten för antalet operationer fokuserar man vanligtvis på konstanter och lägre ordningens termer hos stora indata och ignorerar dem. Den faktiska tiden påverkas av hårdvara, minnesåtkomst och optimeringar som cache eller parallellisering. Därför är två algoritmer med samma asymptotiska klass inte alltid lika snabba i praktiken.

För att förbättra tidskomplexiteten kan man välja bättre algoritm (t.ex. binär sökning istället för linjär), använda effektiva datastrukturer, dela upp problemet (divide and conquer), använda dynamisk programmering eller memoization samt utnyttja parallellisering. Det finns ofta en kompromiss mellan tids- och rymdkomplexitet.