Komplexitet (beräkningsvetenskap)

Från Wikipedia
Hoppa till: navigering, sök
Skall inte förväxlas med komplexa tal.

Komplexitet används för att tala om hur resurskrävande en algoritm eller en funktion är. Normalt analyseras endast det asymptotiska beteendet, och inte bidrag av lägre ordning. För att kunna bedöma komplexiteten hos ett problem måste man först bestämma sig för vilken kostnadsmodell som ska användas. I princip så anger man komplexitet som en funktion av indatats storlek. Man bestämmer först vad storleken av indatan lämpligen mäts i. Därefter tilldelar man kostnader till de grundläggande operationerna i problemet. Är man bara intresserad av den asymptotiska komplexiteten så räcker det att avgöra hur en operations kostnad beror på storleken av indatan. Normalt söker man värsta-falls-komplexiteten, det vill säga komplexiteten för sämst utformade indata. För vissa algoritmer är dock medelkomplexiteten också av intresse.

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)

Komplexitet kan även användas för att tala om hur resurskrävande ett specifikt problem, till exempel sortering, är. Man är då intresserad av att dels försöka hitta en undre gräns till ett problems komplexitet, och dels en övre gräns. Om dessa båda gränser överensstämmer så vet man problemets komplexitet. Att bestämma en övre gräns är enkelt. Det räcker att hitta på en algoritm, och beräkna dess komplexitet. Den lägsta komplexitet man känner för en algoritm att lösa ett problem utgör en övre gräns för problemets komplexitet. För att bestämma en undre gräns krävs ofta avancerade matematiska beräkningar, eller så får man ta till någon trivial undre gräns.

Ordobegreppet[redigera | redigera wikitext]

Mängden data som algoritmen behandlar benämns n. Tidskomplexiteten för algoritmen är då det antal distinkta 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 indatats 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 komplexiteter.

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 nämligen 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[redigera | redigera wikitext]

Datalogiska problem kan delas upp i olika komplexitetklasser 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 ska 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 dom 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[redigera | redigera wikitext]

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[redigera | redigera wikitext]

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. Att addera två tal är enkelt, och 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 av n. Vår algoritm har alltså komplexiteten \mathcal{O}(n).

Se även[redigera | redigera wikitext]