oplossingscomplexiteit

Oplossingscomplexiteit is een begrip uit de informatica dat de hoeveelheid middelen beschrijft die nodig is om een oplossing voor een bepaald probleem te vinden. De middelen omvatten meestal tijd (hoe lang een algoritme draait) en ruimte (het geheugen dat tijdens de uitvoering wordt gebruikt). Deze complexiteit wordt uitgedrukt als een functie van de invoergrootte n en vaak weergegeven met asymptotische notaties zoals Big-O, Big-Theta en Big-Omega.

Er bestaan verschillende perspectieven, waaronder worst-case, gemiddelde-case en beste-case complexiteit. Tijdcomplexiteit geeft aan hoeveel stappen of welke tijd een algoritme nodig heeft; ruimtecomplexiteit hoeveel geheugen wordt verbruikt. Een belangrijk onderscheid is tussen de oplossingscomplexiteit van een specifieke methode en de intrinsieke moeilijkheidsgraad van het probleem zelf, bijvoorbeeld in de classificaties P, NP en NP-volledig. Sommige problemen worden als intrinsiek moeilijk beschouwd (NP-hard), wat betekent dat er geen efficiënte algoritme bestaat die alle gevallen snel oplost.

In de praktijk beïnvloedt oplossingscomplexiteit de ontwerpkeuzes bij softwareontwikkeling. Als de complexiteit hoog is, kan men kiezen voor heuristieken, benaderingen of probabilistische algoritmen, of voor exacte methoden die meer rekentijd toelaten. Reduceringen tussen problemen helpen ook om de verwachte complexiteit van nieuwe problemen in te schatten.

Voorbeelden illustreren het idee: sorteren met vergelijkingssorteringen heeft vaak tijdcomplexiteit O(n log n) in het gemiddelde en worst-case; zoeken in een ongesorteerde lijst kan O(n) zijn; kortste-padproblemen in grafen variëren afhankelijk van de gebruikte techniek.