Komplexitetsteori för beräkning
Teorin om beräkningskomplexitet är en del av datavetenskapen. Man tittar på algoritmer och försöker säga hur många steg eller hur mycket minne en viss algoritm tar för en dator att utföra. Mycket ofta använder algoritmer som använder färre steg mer minne (eller tvärtom: om det finns mindre minne tillgängligt krävs det fler steg för att utföra en algoritm). Många intressanta algoritmer tar ett antal steg som är beroende av problemets storlek.
Olika komplexitetsklasser
Konstant komplexitet
Komplexitetsteorin tittar också på hur ett problem förändras om det görs med fler element. Ett problem med konstant komplexitet är den enda klass där detta inte är sant. Ett problem med konstant komplexitet tar samma antal steg att genomföra oavsett storleken på inmatningen eller antalet element som det beräknas för. Att sända ett meddelande kan betraktas som ett problem med konstant komplexitet. Oavsett hur många personer som behöver ta emot ett meddelande kan alla lyssna på en enda sändning utan att det behövs några extra sändningar.
Linjär komplexitet
Gräsklippning kan ses som ett problem med linjär komplexitet. Det tar dubbelt så lång tid att klippa ett område som är dubbelt så stort som det ursprungliga.
Kvadratisk komplexitet
Antag att du vill veta vilka av dina vänner som känner varandra. Du måste fråga varje par vänner om de känner varandra. Om du har dubbelt så många vänner som någon annan måste du ställa fyra gånger så många frågor för att ta reda på vem alla känner. Problem som tar fyra gånger så lång tid när problemets storlek fördubblas sägs ha en kvadratisk komplexitet.
Logaritmisk komplexitet
Detta är ofta komplexiteten i problem som innebär att man måste slå upp saker, som att hitta ett ord i en ordbok. Om ordboken är dubbelt så stor innehåller den dubbelt så många ord som originalet att jämföra med. Att slå upp något tar bara ett steg mer. Algoritmen för att göra uppslag är enkel. Ordet i mitten av ordboken kommer antingen att vara före eller efter den term som ska sökas upp, om orden inte stämmer överens. Om det är före måste termen finnas i andra halvan av ordboken. Om det är efter ordet måste det finnas i den första halvan. På så sätt halveras problemutrymmet för varje steg, tills ordet eller definitionen har hittats. Detta är allmänt känt som logaritmisk komplexitet.
Exponentiell komplexitet
Det finns problem som växer mycket snabbt. Ett sådant problem är det så kallade Travelling Salesman-problemet. En försäljare måste göra en rundtur i ett visst antal städer. Varje stad ska bara besökas en gång, avståndet (eller kostnaden) för resan ska vara minimalt och säljaren ska hamna där han började. Detta problem är exponentiellt komplext. Det finns n faktoriella möjligheter att ta hänsyn till. Genom att lägga till en stad (från n till n+1) multipliceras antalet möjligheter med (n+1). De flesta intressanta problem har denna komplexitet.
