Grote-O-notatie

Uit Wikipedia, de vrije encyclopedie
(Doorverwezen vanaf Big O notatie)
Ga naar: navigatie, zoeken

De grote-O-notatie of big-O-notatie is in de wiskunde een compacte notatie om voor een functie f(x) aan te geven dat er een constante is zo dat de absolute waarde van de functie kleiner dan of gelijk aan een constante maal een bepaalde eenvoudiger functie g(x) is, als x naar bijvoorbeeld nul of oneindig gaat. Het kan ook gaan om een rij (dit is immers een functie van de index). Een verschil met een limiet van f(x)/g(x) is dat het bij de grote-O-notatie om een ongelijkheid gaat, dus een zwakkere eigenschap.

De notatie wordt in de informatica gebruikt om de (tijds)complexiteitsgraad van algoritmen uit te drukken in termen van een geheel getal als parameter, waarbij het gaat om het aantal elementaire bewerkingen als functie hiervan, als de parameter naar oneindig gaat. Deze notatie is een 'slechtste-geval' maat. Ze geeft enkel informatie over het maximaal aantal elementaire bewerkingen dat een algoritme bij gegeven invoergrootte zal uitvoeren. De notatie is machine-onafhankelijk.

De grote-O notatie heeft bij een rij de volgende vorm:

A = O(g(n))\!

Het komt er bij de genoemde toepassing in de informatica ruwweg op neer dat het aantal elementaire bewerkingen dat een algoritme A bij gegeven invoergrootte n maximaal uitvoert niet harder stijgt als functie van n dan f(n). Formeel:

A = O(g(n)) \Leftrightarrow \exists_{c > 0} \exists_{N \in \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 boven af 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.

Merk op dat (volgens de formele definitie) O(n), O(n2) impliceert. Immers als het algoritme trager of gelijk aan n groeit, dan zeker trager dan n2. Dit is algemeen geldig in de Grote-O-notatie: een lagere complexiteit impliceert een hogere complexiteit.

Veel voorkomende O-functies zijn (in volgorde van stijgende complexiteit):

  • O(1); (constant: 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), (logaritmisch: evenredig aan logaritme van n, als n 10 maal zo groot wordt neemt de tijd met een constante toe)
  • O(n), (lineair: tijd evenredig aan n)
  • O(n log n), (linearitmisch: product van de vorige twee - dit is de complexiteit van de beste sorteeralgoritmen die bekend zijn)
  • O(n2) (kwadratisch: tijd neemt kwadratisch toe met de grootte van het probleem)
  • O(2n) (exponentieel: tijd neemt exponentieel toe met de grootte van het probleem)

Algoritmen met een complexiteit O(nk) met k \in \N (en n de invoergrootte) noemen we polynomiaal. Algoritmen met een complexiteit O(kn) met k \in \N noemen we exponentieel. Merk opnieuw op dat polynomiale algoritmen exponentiëel zijn, maar omgekeerd niet.