Komplexitet (beräkningsvetenskap)

Skall inte förväxlas med komplexa tal.

Komplexitet beskriver inom beräkningsvetenskap hur omfattande och resurskrävande ett problem är. Vanligen löses beräkningsproblem med hjälp av en algoritm.

Den lägsta komplexitet man känner till för en algoritm att lösa ett problem utgör en övre gräns för problemets komplexitet. När ett problems komplexitet ska bestämmas väljer man först en lösningsmodell och vilken storlek indata mäts i. För att bestämma en undre gräns krävs ofta matematiska beräkningar eller användningen av en trivial gräns. När den övre och undre gränsen överensstämmer med varandra har man bestämt problemets komplexitet.

Inom datorprogrammering finns mätmetoder för att kvantitativt bestämma komplexitet av en metod/funktion eller en modul/klass:

McCabe-tal, eller cyklomatisk komplexitet, som anger antal vägar genom en metod
Efferent Couplings, antal beroenden till andra metoder, moduler eller klasser (till exempel referenser till externa data, metoder etc.)
Infferent Couplings, antal beroenden från andra metoder, moduler eller klasser (till exempel referenser till externa data, metoder etc.)
antal rader kod per metod, klass/modul
arvsdjup (för klasser)

Ordobegreppet

Mängden data som algoritmen behandlar benämns n. Tidskomplexiteten för algoritmen är antalet steg algoritmen kan behöva för att slutföra en beräkning, uttryckt som en funktion av datamängden n. Exempelvis, ett datorprogram som ska hitta platsen för ett visst element i en osorterad lista behöver i värsta fallet titta på varje element i listan. Ett sådant program får då tidskomplexiteten O(n), där O står för ordo. Ett program som tar konstant tid oavsett indata-storlek, exempelvis en uppslagning i en hashtabell, får O(1). Notera att tiden för varje steg i algoritmen i allmänhet är ointressant. Skulle man exempelvis komma fram till O(12n²) för en algoritm så anger man ändå bara O(n²). Detta eftersom skalfaktorn alltid blir insignifikant för tillräckligt stora värden på n, när man jämför algoritmer med olika komplexitetsklasser.

På motsvarande sätt definieras minneskomplexitet, där det maximala använda minnet under algoritmens gång är det intressanta.

Formellt betyder $f(n)\in O(g(n))$ att det finns positiva konstanter N och c så att $f(n)\leq c\cdot g(n)$ för alla $n>N$ , vilket ska uttydas som att f(n) inte växer snabbare än g(n). Det är alltså inte det faktiska antalet steg i en algoritm man är ute efter (det är ofta starkt implementationsbundet) utan det asymptotiska uppträdandet: om datastorleken dubbleras, hur mycket mer tid kommer det då att ta? Om algoritmen är O(n) dubbleras även körtiden, men om algoritmen är O(n²) så kommer det att ta fyra gånger så lång tid.

När man inom datalogin skriver $O(g(n))$ menar man egentligen $\Theta (g(n))$ . Det är fullt korrekt att säga att en $O(n)$ -algoritm är av komplexiteten $O(n^{2})$ , vilket inte gäller för Θ.

Notation	Definition
$f(n)\in O(g(n))$	$\limsup _{x\to \infty }\left\|{\frac {f(x)}{g(x)}}\right\|<\infty$
$f(n)\in \Theta (g(n))$	$f\in O(g)$ och $g\in O(f)$

Komplexitetsklasser

Datalogiska problem kan delas upp i olika komplexitetsklasser baserat på hur mycket resurser som behövs för att lösa det samt vilka operationer som är tillåtna.

Några viktiga komplexitetsklasser är P, som brukar representera problem där praktiskt tillämpbara algoritmer, och NP, där det endast är praktiskt möjligt att verifiera en lösning. Bokstaven P står för "polynomiell komplexitet" och ett beräkningsproblem ([beslutsproblem] om man skall vara noggrann) är i P om det finns en algoritm med en polynomiell värsta-fallet komplexitet, dvs den är $O(n^{c})$ för någon konstant $c$ . För NP, som står för non-deterministic polynomial time, alltså icke-deterministisk polynomiell tid, känner man bara till en algoritm som löser problemet i polynomiell tid om beräkningsmodellen är icke-deterministisk. Detta brukar uttryckas som att lösningar till problemet kan verifieras i polynomiell tid. Notera att $P\subseteq NP$ . Ett av den teoretiska datalogins stora olösta problem är om $P\not =NP$ .

Ytterligare ett viktigt begrepp NP-fullständighet, ibland direktöversatt från engelskan till NP-komplett, som inbegriper de i viss mening svåraste problemen i NP. Dessa har identifierats i förhoppning om att kunna avgöra om $P\not =NP$ , men detta har hittills varit fruktlöst. Däremot har begreppet varit användbart för att identifiera problem som är i praktiken ogörliga att hantera på ett bra sätt när indata-storleken växer. Ett problem A är NP-fullständigt om det är i NP och man kan reducera varje annat problem i NP till A. Ett annat sätt att se det på är att säga att det är minst lika svårt som varje annat problem i NP.

Undre gränser

Algoritmers komplexitet kan ses som övre gränser för hur svårt ett problem är. För att kunna avgöra om det finns ännu effektivare algoritmer för att problem kan det också vara intressant att reflektera över om det finns undre gränser för tidskomplexiteten. Med andra ord, finns det någon gräns för hur effektiva algoritmer man kan hitta för ett visst beräkningsproblem?

Här använder man sig av ett begrepp som är relaterat till ordo-begreppet. För två funktioner f och g gäller att $f\in \Omega (g(n))$ om $g\in O(f(n))$ . Med hjälp av Ω säger man alltså att funktionen f växer minst lika snabbt som g.

Det är ofta svårt att hitta undre gränser eftersom man på ett rigoröst matematiskt sätt måste visa att det verkligen inte finns någon algoritm som är mer effektiv. Det klassiska exemplet på en undre gräns gäller för sortering i en beräkningsmodell där man räknar antalet jämförelser. Då kan man visa att den undre gränsen är $\Omega (n\log n)$ . Detta råkar matcha effektiviteten på flera sorteringsalgoritmer, som alltså är $O(n\log n)$ , och man kan därför säga att sorteringsproblemet är $\Theta (n\log n)$ .

Exempel

En mycket enkel algoritm för att multiplicera två positiva tal, $a$ och $b$ är: Låt $a$ vara det största av talen och $b$ det minsta talet och beräkna $\sum _{i=1}^{b}a$ . Indatan är här de båda talen $a$ och $b$ . Vi genomför två operationer: jämförelse och summering. Summering kan ses som en serie enkla additioner av två tal. En sådan operation är så pass enkel att vi kan säga att det har en konstant kostnad, $C_{1}$ . Även att jämföra två tal är enkelt och har också konstant kostnad, $C_{2}$ . Att utföra samma typ av beräkning, med kostnad $C_{1}$ , $n$ gånger kostar $n\cdot C_{1}$ . Den totala kostnaden för multiplikationen blir då $C_{2}+n\cdot C_{1}$ . Vi har här valt $n$ som mått på indatans storlek under beräkningens gång genom att inse att det som påverkar kostnaden endast beror på $n$ . Vår algoritm har alltså komplexiteten ${\mathcal {O}}(n)$ .

Se även