Landauova notace

Landauova notace (též notace velké O nebo notace omikron) je notace používaná v matematice pro porovnávání asymptotického chování funkcí, tj. chování funkcí pro „velké“ hodnoty parametru. V matematické informatice se tato notace používá pro porovnání asymptotické časové nebo prostorové složitosti algoritmů, případně pro omezení složitosti algoritmu. Je-li nějaká funkce z množiny ${\mathcal {O}}(h^{2})$, znamená to, že se chová přibližně jako kvadratická funkce. Tedy v nekonečnu roste rychleji, než lineární funkce, která je z množiny ${\mathcal {O}}(h)$. Při pohledu na chování v okolí počátku, funkční hodnoty funkce z množiny ${\mathcal {O}}(h^{2})$ se blíží k nule rychleji, než je tomu u lineární funkce.^[zdroj?]

Formální definice

Nechť $f(x)$ a $g(x)$ jsou dvě funkce definované na nějaké podmnožině reálných čísel. Potom lze říci, že

$f(x)\in {\mathcal {O}}(g(x))$

právě tehdy když

$\exists (C>0),x_{0}:\forall (x>x_{0})\;|f(x)|\leq |Cg(x)|$

Alternativně se zápis definuje pro reálné funkce, jejichž definiční obor je množina přirozených čísel.

Definici je možné modifikovat pro popis asymptotického chování v nule namísto nekonečna.

Další používané notace

Notace	Význam	Definice
$f(x)\in {\mathcal {O}}(g(x))$	$f$ je asymptoticky ohraničena funkcí $g$ shora (až na konstantu)	$\exists (C>0),x_{0}:\forall (x>x_{0})\;|f(x)|\leq |Cg(x)|$
$f(x)\in \Omega (g(x))$	$f$ je asymptoticky ohraničena funkcí $g$ zdola (až na konstantu)	$\exists (C>0),x_{0}:\forall (x>x_{0})\;|Cg(x)|\leq |f(x)|$
$f(x)\in \Theta (g(x))$	$f$ je asymptoticky ohraničena funkcí $g$ z obou stran (až na konstantu)	$\exists (C,C'>0),x_{0}:\forall (x>x_{0})\;|Cg(x)|<|f(x)|<|C'g(x)|$
$f(x)\in o(g(x))$	$f$ je asymptoticky ohraničena funkcí $g$ shora ostře	$\forall (C>0),\exists x_{0}:\forall (x>x_{0})\;|f(x)|<|Cg(x)|$
$f(x)\in \omega (g(x))$	$f$ je asymptoticky ohraničena funkcí $g$ zdola ostře	$\forall (C>0),\exists x_{0}:\forall (x>x_{0})\;|Cg(x)|<|f(x)|$
$f(x)~\sim g(x)$	asymptoticky rovné	$\lim _{x\to \infty }{\frac {f(x)}{g(x)}}=1$

Vztahy mezi množinami

$\Theta (g(x))={\mathcal {O}}(g(x))\cap \Omega (g(x))$

Příklad

Aproximace derivace pomocí centrální diference vzorcem

$${\frac {\mathrm {d} f}{\mathrm {d} x}}=f'(x)={\frac {f(x+h)-f(x-h)}{2h}}+{\mathcal {O}}(h^{2})$$

ukazuje, že při nahrazení derivace $f'(x)$ podílem ${\frac {f(x+h)-f(x-h)}{2h}}$ je chyba srovnatelná s druhou mocninou hodnoty $h$. Tato aproximace je přesnější, než použití dopředné diference

$${\frac {\mathrm {d} f}{\mathrm {d} x}}=f'(x)={\frac {f(x+h)-f(x)}{h}}+{\mathcal {O}}(h),$$

kde je chyba srovnatelná "pouze" s první mocninou hodnoty $h$. V praxi totiž bývá hodnota $h$ blízká k nule a tam druhá mocnina ubývá rychleji, například pro $h=0.01$ je $h^{2}=0.0001$, což dává dvojnásobný počet desetinných míst.^[zdroj?]

Odkazy

Externí odkazy

• Odhady složitosti Archivováno 24. 2. 2016 na Wayback Machine. (česky)

Autoritní data	PSH: 7768