Complexiteitsgraad

Principes

Computationele complexiteitstheorie

Modellen

Algoritme

Theorieën

De complexiteitsgraad van een bepaald algoritme is de manier waarop dat algoritme zich gedraagt als de grootte van het op te lossen probleem toeneemt.

Principes van complexiteit

De basis

De bestudering van de complexiteit van een gegeven algoritme is een van de centrale bezigheden van de tak van wiskunde en informatica die bekendstaat als complexiteitstheorie. Binnen de complexiteitstheorie wordt onder meer gekeken naar hoe een gegeven wiskundig probleem precies opgelost wordt – letterlijk in de zin van "Welke stappen moeten ondernomen worden om van een probleemstelling tot een oplossing te komen?"

Om deze vraag te kunnen beantwoorden, worden berekeningen in de complexiteitstheorie beschreven met een model van hoe berekeningen plaatsvinden: de zogeheten turingmachine. In dit model – dat het oplossen van problemen uiterst mechanisch benadert – wordt iedere berekening opgedeeld in een aantal zeer kleine stappen. Het aantal benodigde stappen om tot een oplossing van het probleem te komen, is de tijdscomplexiteit van het probleem.

Behalve de tijdscomplexiteit bestudeert men soms ook de ruimtecomplexiteit. De ruimtecomplexiteit betreft de relatie tussen probleemgrootte en de hoeveelheid geheugen die bij de berekening wordt gebruikt. Wanneer men spreekt van complexiteit zonder verdere aanduiding, wordt meestal in eerste instantie de tijdscomplexiteit bedoeld.

Algoritmen

De complexiteitstheorie bekijkt de complexiteit van problemen echter in een algemenere zin dan te kijken naar ieder individueel probleem. Kijken naar iedere individuele opgave zou trouwens ook niet kunnen: bedenk dat je iedere twee natuurlijke getallen bij elkaar op kunt tellen en er zijn oneindig veel problemen om op te lossen. Bovendien is het bekijken van (bijvoorbeeld) iedere individuele optelling ook niet erg interessant.

De complexiteitsleer interesseert zich veel meer voor het bepalen van de complexiteit van hele klassen van problemen tegelijk – niet "wat is de complexiteit van het oplossen van 2 + 3", maar "wat is de complexiteit van een algemene methode om twee natuurlijke getallen bij elkaar op te tellen". Gelukkig staat het turingmachinemodel dit toe: het is mogelijk om voor een turingmachine een programma te schrijven, wederom in de vorm van een aantal simpele stappen die vaak herhaald worden, dat een hele klasse van problemen oplost. De complexiteitstheorie bestudeert de complexiteit van dit soort "programma's", algemene stappenplannen die een hele klasse van problemen oplossen. Een dergelijk stappenplan wordt overigens een algoritme genoemd.

Relatieve complexiteit

Uiteraard is het niet mogelijk om bij het bestuderen van een hele klasse van problemen een directe uitspraak te doen over de complexiteit. Hoe je het ook wendt of keert, het uitvoeren van het product

234456597356 * 976895793565

duurt langer dan het uitvoeren van het product

5 * 6

zelfs al is de algemene methode van oplossen hetzelfde.

Om toch algemenere uitspraken te kunnen doen over de complexiteit van algoritmes, drukt de complexiteitstheorie de complexiteit van een algoritme uit in termen van het aantal stappen dat een gegeven algoritme nodig heeft ten opzichte van de grootte van de invoer.

Uiteraard is het daarvoor wel nodig dat voor iedere invoer een concept van "grootte" bestaat. Gelukkig is dat geen probleem – het turingmachinemodel is dusdanig dat iedere invoer een grootte moet hebben (het benodigde aantal posities op de band). De complexiteit van een gegeven algoritme wordt nu uitgedrukt in het aantal stappen dat het algoritme moet zetten om tot een oplossing te komen, ten opzichte van de grootte van de invoer. Bijvoorbeeld, als een invoer de grootte

N

heeft, dan zou gezegd kunnen worden dat de complexiteit van een gegeven algoritme gelijk is aan

N^{2}-3N+7

Complexiteit en orde-groottes

Grootte-ordes

Zoals hierboven beschreven, wordt de complexiteit van een gegeven algoritme uitgedrukt in termen van de grootte van de invoer voor dat algoritme. Dit leidt voor ieder algoritme A tot een uitdrukking die de complexiteit C(A) van A weergeeft. Door het bestaan van dergelijke uitdrukkingen wordt het mogelijk om algoritmen met elkaar te vergelijken, wat complexiteit betreft.

Naast directe vergelijking, maakt de complexiteitsleer echter ook gebruik van een wat grovere indeling van algoritmen naar complexiteit, de zogeheten grootte-ordes. Zoals we zullen zien zijn grootte-ordes niet erg precies. Maar ze hebben wel het voordeel dat je algoritmen langs grote lijnen in kunt delen in een overzichtelijke hiërarchie van klassen van algoritmen. En dat vinden wiskundigen fijn, want een dergelijke hiërarchie maakt het mogelijk om in abstractere zin te redeneren over het geheel van al de oneindige aantallen algoritmen die je mogelijk zou kunnen verzinnen.

Bij de grootte-orde van een algoritme A wordt alleen maar gekeken naar het deel van de uitdrukking C(A) dat de grootte van C(A) het meest bepaalt. Hadden we eerder het voorbeeld dat de exacte complexiteit van een algoritme gelijk was aan

N^{2}-3N+7

dan geldt dat de grootte-orde van dit algoritme simpelweg gelijk is aan $N^{2}$ . We zeggen dan dat het algoritme kwadratisch is qua grootte-orde. Hetzelfde geldt voor lineare algoritmen (grootte-orde $N$ ), kubisch ( $N^{3}$ ), vierde-machts ( $N^{4}$ ) en zelfs exponentieel (bijvoorbeeld $2^{N}$ ).

Orde-notaties

Er zijn verschillende manieren om grootte-ordes van algoritmen weer te geven, die allemaal gebruikmaken van een polynomiale uitdrukking. Deze notaties hebben echter allemaal een eigen betekenis, een eigen idee dat tot uitdrukking gebracht wordt.

De belangrijkste orde-notaties die gebruikt worden, geven aan dat een gegeven algoritme ten hoogste een bepaalde complexiteit heeft, ten minste een bepaalde complexiteit heeft en precies een bepaalde complexiteit heeft.

Begrenzing van boven

Begrenzing van boven drukt uit dat een gegeven algoritme A ten hoogste een bepaalde complexiteit heeft. Deze begrenzing van A wordt vaak aangegeven met een notatie die in de wiskunde de "grote-O" notatie genoemd wordt (maar eigenlijk is het niet een O, maar een hoofdletter omicron, de Griekse letter).

De grote-O notatie heeft de volgende vorm:

A=O(f(N))

wat wil zeggen de complexiteit van A is ten hoogste een uitdrukking f(N); deze uitdrukking is een polynoom in N, waarbij N de grootte is van de invoer.

Formeel is de betekenis van de grote-O notatie als volgt gedefinieerd:

A=O(g(n))\Leftrightarrow \exists _{c>0}\exists _{N\in \mathbb {N} }\forall _{n\geq N}:0\leq A(n)\leq c\cdot g(n)

Het bovenstaande wil zeggen: vanaf een bepaalde invoergrootte N wordt A van bovenaf begrensd door functie g, maal een constante factor c. Oftewel: vanaf probleemgrootte N is de waarde g(n) altijd groter dan het aantal stappen dat A nodig heeft om een probleem met invoergrootte n op te lossen. Daarmee is g een bovengrens voor de complexiteit van A.

Veel voorkomende O-functies zijn

O(1); (tijd onafhankelijk van de grootte van het probleem; preciezer: de tijd is nooit meer dan een bepaalde bovengrens, ook al is het probleem nog zo groot)
O(log n), (evenredig aan logaritme van n, als n een grootte-orde toeneemt neemt de tijd met een constante toe)
O(n), (tijd evenredig aan n)
O(n log n), (product van de vorige twee - dit is de complexiteit van de beste sorteer-algoritmen die bekend zijn)
O(n²) (tijd neemt kwadratische toe met de grootte van het probleem)
O(2ⁿ) (tijd neemt exponentieel toe met de grootte van het probleem)

Begrenzing van onder

Analoog aan de grote-O notatie voor begrenzing van boven, kennen we ook een notatie die aangeeft dat een algoritme ten minste een bepaalde complexiteit heeft: de grote-omega notatie. Deze heeft een soortgelijke vorm als die van de grote-O notatie:

A=\Omega (f(N))

De formele definitie van deze notatie is als volgt:

A=\Omega (g(n))\Leftrightarrow \exists _{c>0}\exists _{N\in \mathbb {N} }\forall _{n\geq N}:0\leq c\cdot g(n)\leq A(n)

Oftewel, vanaf een bepaalde invoergrootte N wordt A van onder af begrensd door functie g, maal een constante factor c.

De bekende grootte-ordes die we gezien hebben bij de grote-O notatie zijn ook veelvoorkomend bij de grote-omega notatie.

Precieze orde

Ten slotte is er de precieze begrenzing (binnen een bepaald, constant interval van afwijking). Hiervoor wordt een hoofdletter thèta gebruikt en een begrenzing van grote-thèta-orde is eigenlijk zowel een begrenzing van boven als van beneden.

De formele definitie van deze begrenzing is:

A=\Theta (g(n))\Leftrightarrow \exists _{c_{1},c_{2}>0}\exists _{N\in \mathbb {N} }\forall _{n\geq N}:0\leq c_{1}\cdot g(n)\leq A(n)\leq c_{2}\cdot g(n)

Oftewel, vanaf een bepaalde invoergrootte N wordt A van boven en van onder af begrensd door functie g, met een "bewegingsruimte" bepaald door $c_{1}$ en $c_{2}$ .

P en NP

Naast de bovengenoemde indeling in een hiërarchie van complexiteit, kent de complexiteitstheorie nog een indeling: makkelijke en moeilijke problemen.

De makkelijke problemen zijn die problemen waarvoor een algoritme bekend is met een tijdscomplexiteit die een polynomiale uitdrukking is in de grootte van de invoer. Deze problemen vormen samen de verzameling P van in polynomiale tijd oplosbare problemen.

De moeilijke problemen zijn de problemen waarvoor een dergelijk algoritme niet bekend is.

Van een groot aantal problemen is geen snel algoritme bekend; van een deel daarvan is bewezen dat zo'n algoritme niet kan bestaan. Wel zijn voor een groot aantal van deze 'computationeel moeilijke' problemen algoritmen bekend die niet met zekerheid de beste, maar wel een goede oplossing geven, zogenaamde heuristische methoden.

Een eigenaardige klasse wordt gevormd door de NP problemen. Hoewel voor veel van deze problemen geen polynomiaal algoritme bekend is, geldt voor alle NP problemen dat een gegeven kandidaat-oplossing wel in polynomiale tijd gecontroleerd kan worden op correctheid (NP staat voor 'niet-deterministische polynomiaal').

Binnen NP vormen de NP-volledige problemen een bijzondere groep. Er is bewezen dat ieder probleem in de verzameling van NP-problemen in polynomiale tijd omgeschreven kan worden naar een NP-volledig probleem. Dat wil zeggen, als je een algoritme hebt om een enkel NP-volledig probleem op te lossen, kun je dat algoritme gebruiken om ieder probleem in NP op te lossen. Als er dus ooit een polynomiaal algoritme wordt gevonden voor een NP-volledig probleem, kunnen daarmee alle NP-problemen in polynomiale tijd worden opgelost, waaruit zou volgen dat de verzameling NP gelijk is aan de verzameling P. Dit is een van de zwaardere onderzoeksgebieden binnen de complexiteitstheorie.

Voorbeelden van NP-complete problemen zijn het handelsreizigersprobleem en het vervulbaarheidsprobleem.

Zie ook