De complexiteitsgraad van een bepaald algoritme is de manier waarop dat algoritme zich gedraagt als de grootte van het op te lossen probleem toeneemt. Hierbij wordt vaak gebruik gemaakt van de O-notatie: een complexiteit van O(n2) geeft aan dat de voor het oplossen van het probleem benodigde tijd evenredig is met het kwadraat van n, waarbij n een maat is voor de grootte van het probleem, en deze n willekeurig groot kan zijn. Bij een sorteeralgoritme zal n bijvoorbeeld staan voor het aantal elementen dat moet worden gesorteerd. Formeel geldt dat een functie f(n) O(n2) is als f(n)2, voor zekere constante a, vanaf zekere waarde van n.
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(n2) (tijd neemt toe met kwadraat van probleem)
- O(2n) (tijd neemt exponentieel toe met de grootte van het probleem)
Natuurlijk zal een algoritme op een supercomputer sneller kunnen worden afgewerkt dan op een ouderwetse personal computer, en bij een programma in BASIC langzamer dan wanneer het programma in geoptimaliseerde machinetaal is geschreven, maar het verschil bedraagt een constante factor. Een exponentiële O-functie wordt zo snel groter bij toename van de grootte van het probleem dat er zelfs bij de supercomputer al snel problemen optreden die om praktische redenen niet meer op te lossen zijn omdat het astronomisch lang zou gaan duren het algoritme uit te voeren. Als n klein is zal men nog wel eens een algoritme willen kiezen dat eenvoudiger te programmeren is, of dat voor kleine waarden sneller is, maar als men met grote problemen moet werken, is het altijd aan te raden om het algoritme met de kleinste complexiteitsgraad te nemen. Zoiets zal dan vaak meer verbetering brengen dan bijvoorbeeld gebruik te maken van snellere apparatuur.
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 bepaalde klasse van moeilijke problemen waarvoor de complexiteitsgraad nog niet door een polynoom kan worden beschreven vormen de groep van NP-moeilijke problemen. Dit zijn problemen waarvoor er geen polynomiaal algoritme bestaat, maar waarvan bij een eventuele oplossing wel in polynomiale tijd gecontroleerd kan worden of het correct is (NP staat voor 'non-deterministische polynomiaal'). Een speciale groep hierbinnen zijn de NP-complete problemen. Als men enig NP-compleet probleem in polynomiale tijd (dat wil zeggen met complexiteit nk voor zekere k) zou kunnen oplossen, kan men daarmee elk NP-moeilijk probleem oplossen in polynomiale tijd oplossen.
Voorbeelden van NP-complete problemen zijn: het handelsreizigersprobleem, het ontbinden van een getal in priemfactoren, ... De exponentiële vorm van de complexiteitsgraad voor deze problemen zorgt ervoor dat bijvoorbeeld voor het handelsreizigersprobleem een probleem van 20 steden helemaal geen probleem is en op elke eenvoudige computer kan worden opgelost; toevoegen van 2 steden maakt het probleem zo moeilijk dat er een supercomputer aan te pas komt, en toevoegen van nog 2 steden maakt het in de praktijk onmogelijk op te lossen.
Het is een nog onopgelost probleem in de complexiteitstheorie of er een polynomiale oplossing voor de NP-complete problemen bestaat (dat wil zeggen, of P=NP, waar P de klasse van problemen is die in polynomiale tijd zijn op te lossen), maar vrijwel iedereen gaat ervan uit dat een dergelijk algoritme niet bestaat.
zie ook berekenbaarheid.
