tidkompleksitet

Tidskomplexitet, ibland kallad tidkomplexitet, är ett mått på hur lång tid en algoritm förväntas ta att köra som funktion av problemstorleken n. Den används för att jämföra algoritmer oberoende av maskinvara och konstanter, och beskriver hur tiden växer när n ökar.

Notationen Big-O, Big-Theta och Big-Omega beskriver övre, exakt och nedre tillväxt. Genom att använda dem kan man uttrycka att en algoritm har tidskomplexitet som till exempel O(1), O(log n), O(n), O(n log n), O(n^2), eller O(2^n). Dessa är asymptotiska mått som fokuserar på hur tiden växer när n går mot oändligheten och lämnar konstanter och lägre ordningens termer osynliga.

Tidkomplexitet kan anges som worst-case (övre gräns som alltid uppfylls), best-case (lägsta möjliga tid), och average-case (förväntad tid under givna antaganden om indata). Valet av scenarie påverkar vad som anses vara en rimlig prestanda i praktiken.

Analys av tidskomplexitet innebär ofta att formulera en rekursiv relation eller räkna antalet grundoperationer i varje steg och eventuella rekursioner. Lösningar kan erhållas med hjälp av verktyg som masterteoremet eller genom noggrann uppföljning av algoritmens loopar och operationer.

Exempel: binärsökning har tidskomplexitet O(log n), eftersom varje jämförelse halverar sökintervallet. Linjärt sök i en osorterad lista har O(n). Generell sortsalgoritm med jämförelser har i genomsnitt O(n log n) tid, medan bubbelsort ofta har O(n^2) i värsta fallet. Vissa problem kräver exponentiell tid i storlek av indata i bitrepresentation.

Tidskomplexitet är ett teoretiskt verktyg som hjälper till att bedöma hur skiftande algoritmer skalar med större problem, oberoende av maskinvarans hastighet. Reelitering kräver ofta antaganden om indata och operationernas kostnad, vilket kan påverka verklig prestanda.