Computationele complexiteitstheorie
Computationele complexiteitstheorie is een onderdeel van computerwetenschap. Het kijkt naar algoritmen, en probeert te zeggen hoeveel stappen of hoeveel geheugen een bepaald algoritme nodig heeft om een computer te laten werken. Heel vaak gebruiken algoritmen die minder stappen gebruiken meer geheugen (of omgekeerd: als er minder geheugen beschikbaar is, kost het meer stappen om het te doen). Veel interessante algoritmen nemen een aantal stappen dat afhankelijk is van de grootte van het probleem.
Verschillende klassen van complexiteit
Constante complexiteit
De complexiteitstheorie bekijkt ook hoe een probleem verandert als het voor meer elementen wordt gedaan. Een probleem van constante complexiteit is de enige klasse waarin dit niet geldt. Een probleem met constante complexiteit neemt hetzelfde aantal stappen om te voltooien, ongeacht de grootte van de invoer of het aantal elementen waarop het berekend wordt. Het uitzenden van een bericht kan worden beschouwd als een probleem van constante complexiteit. Het maakt niet uit hoeveel mensen een bericht moeten ontvangen, ze kunnen allemaal luisteren naar een enkele uitzending zonder dat er extra uitzendingen nodig zijn.
Lineaire complexiteit
Grasmaaien kan worden beschouwd als een probleem van lineaire complexiteit. Het maaien van een gebied dat twee keer zo groot is als het oorspronkelijke duurt twee keer zo lang.
Kwadratische complexiteit
Stel dat je wilt weten welke van je vrienden elkaar kennen. Je moet elk paar vrienden vragen of ze elkaar kennen. Als je twee keer zoveel vrienden hebt als iemand anders, moet je vier keer zoveel vragen stellen om erachter te komen wie iedereen kent. Problemen die vier keer zo lang duren als de omvang van het probleem verdubbelt, worden kwadratisch complex genoemd.
Logaritmische complexiteit
Dit is vaak de complexiteit voor problemen waarbij dingen moeten worden opgezocht, zoals het vinden van een woord in een woordenboek. Als het woordenboek twee keer zo groot is, bevat het twee keer zoveel woorden als het origineel om mee te vergelijken. Iets opzoeken kost slechts één stap meer. Het algoritme om opzoekingen te doen is eenvoudig. Het woord in het midden van het woordenboek staat voor of na de op te zoeken term, als de woorden niet overeenkomen. Als het ervoor staat, moet de term in de tweede helft van het woordenboek staan. Als hij na het woord staat, moet hij in de eerste helft staan. Op die manier wordt de probleemruimte bij elke stap gehalveerd, totdat het woord of de definitie is gevonden. Dit is algemeen bekend als logaritmische complexiteit.
Exponentiële complexiteit
Er zijn problemen die heel snel groeien. Eén zo'n probleem staat bekend als het Reizende Verkoper-probleem. Een verkoper moet een rondreis maken langs een bepaald aantal steden. Elke stad mag maar één keer bezocht worden, de afstand (of kosten) van het reizen moeten minimaal zijn, en de verkoper moet eindigen waar hij begon. Dit probleem is exponentieel complex. Er zijn n factorial mogelijkheden om te overwegen. Door één stad toe te voegen (van n naar n+1) wordt het aantal mogelijkheden vermenigvuldigd met (n+1). De meeste interessante problemen hebben deze complexiteit.
