Grote-O-notatie

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

De Grote-O-notatie of Big-O-notatie wordt in de informatica gebruikt om de (tijds)complexiteitsgraad van algoritmen uit te drukken. 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 de volgende vorm:

A = O(f(n))\!

Informeel komt het erop neer dat een algoritme A bij gegeven invoergrootte n (groot genoeg) steeds minder dan f(n) elementaire bewerkingen zal uitvoeren. Formeel is de betekenis van de grote-O notatie als volgt gedefinieerd:

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 een grootte-orde toeneemt 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 kwadratische 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 exponentiële algoritmen polynomiaal zijn, maar omgekeerd niet.