Grote-O-notatie

In de wiskunde is de grote-O-notatie, ook het grote-O-symbool, een van de Landau-symbolen waarmee op compacte wijze aangegeven kan worden dat een functie asymptotisch gedomineerd wordt door een andere functie. Meestal is de dominerende functie van een eenvoudige vorm, zodat een overzichtelijke indruk verkregen wordt van het asymptotische gedrag van de doelfunctie.

Een andere manier om het asymptotische gedrag van de ene functie $f$ te vergelijken met een andere functie $g$ is het bepalen van de relevante limiet van het quotiënt $f(x)/g(x)$. Bij de grote-O-notatie gaat het slechts om een ongelijkheid, dus dat is een zwakkere eigenschap.

Definitie

Men zegt dat de functie $f:\mathbb {R} \to \mathbb {R}$ zich voor $x\to \infty$ gedraagt als grote O van $g:\mathbb {R} \to \mathbb {R}$, en noteert

$f(x)=O(g(x))\ (x\to \infty )$

of

$f(x)\in O(g(x))\ (x\to \infty )$,

als er een positief getal $M\in \mathbb {R} ,\ M>0$ en een getal $x_{0}\in \mathbb {R}$ is, zodanig dat voor $x>x_{0}$ geldt

$|f(x)|\leq M\,|g(x)|$

Dit houdt in dat voor voldoend grote $x$ $f(x)$ in absolute waarde begrensd wordt door $M\,|g(x)|$.

Analoog wordt de notatie gebruikt om het gedrag van $f$ in de buurt van een punt $a\in \mathbb {R}$ te karakteriseren.

$f(x)=O(g(x))\ (x\to a)$

of

$f(x)\in O(g(x))\ (x\to a)$,

als er positieve getallen $M,\delta \in \mathbb {R} ,\ M,\delta >0$ zijn, zodanig dat voor $|x-a|<\delta$ geldt

$|f(x)|\leq M\,|g(x)|$

Dit houdt in dat voor waarden van $x$ in de buurt van $a$ $f(x)$ in absolute waarde begrensd wordt door $M\,|g(x)|$.

Notatie

De notatie met het '='-teken is historisch bepaald, maar maakt eigenlijk misbruik van dat teken. In wezen wordt in de uitspraak: "$f(x)$ is $O(g(x))$" het woordje 'is' als '=' geschreven. De modernere notatie met '$\in$'-teken is daarentegen wel correct, als met $O(g(x))$ de verzameling functies aangeduid wordt die de bedoelde eigenschap bezitten. Deze verzameling functies is een lineaire ruimte, zoals eenvoudig aangetoond kan worden.

Met $f_{1}(x)=f_{2}(x)+O(g(x))$ wordt bedoeld $f_{1}(x)-f_{2}(x)=O(g(x))$.

Geschiedenis

Het symbool (grote) O, dat een afkorting is van 'orde', werd voor het eerst gebruikt door de Duitse getaltheoreticus Paul Bachmann in de in 1894 verschenen 2e druk van zijn boek Analytische Zahlentheorie. Bekendheid kreeg de notatie door de eveneens Duitse getaltheoreticus Edmund Landau, wiens naam met de symboliek verbonden is.

Voorbeelden

Asymptotisch geldt:

$x^{3}+2x^{2}-4x+3\in O(x^{3})$,

wat ook te begrijpen is, omdat voor grote $x$ de term met de hoogste macht, $x^{3}$, overheerst.

Met de grote-O notatie kan de restterm beschreven worden in de benadering van een functie.

$e^{x}=1+x+{\tfrac {1}{2}}x^{2}+O(x^{3})\quad (x\to 0)$

waarmee uitgedrukt wordt dat het verschil $e^{x}-(1+x+{\tfrac {1}{2}}x^{2})$ voor waarden van $x$ dicht bij 0 en zekere $M$ kleiner is dan $|Mx^{3}|$.

Informatica

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.

Algoritmen met een complexiteit $O(n^{k}),\ \ k\in \mathbb {N}$ (en $n$ de invoergrootte) heten polynomiaal. Algoritmen met een complexiteit $O(k^{n}),\ \ k\in \mathbb {R}$, $k>1$ heten exponentieel. Merk opnieuw op dat polynomiale algoritmen exponentieel zijn, maar omgekeerd niet.

Merk op dat $O(n)$ tevens $O(n^{2})$ impliceert. Immers als het algoritme trager of gelijk aan $n$ groeit, dan zeker trager dan $n^{2}$. Dit is algemeen geldig in de grote-O-notatie: een lagere complexiteit impliceert een hogere complexiteit.

Veel voorkomende ordes voor 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(n^{2})$: kwadratisch: tijd neemt kwadratisch toe met de grootte van het probleem;
• $O(2^{n})$: exponentieel: tijd neemt exponentieel toe met de grootte van het probleem.
• $O(n!)$: berekenen van permutaties: tijd is evenredig met n faculteit.

Bronnen, noten en/of referenties