Asymptotická 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 ${\displaystyle {\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 ${\displaystyle {\mathcal {O}}(h)}$. Při pohledu na chování v okolí počátku, funkční hodnoty funkce z množiny ${\displaystyle {\mathcal {O}}(h^{2})}$ se blíží k nule rychleji, než je tomu u lineární funkce.^[zdroj?]

Formální definice

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

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

právě tehdy když

${\displaystyle \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.^[1][2]

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

Vztahy mezi množinami

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

Příklad

Aproximace derivace pomocí centrální diference vzorcem $${\displaystyle {\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 ${\displaystyle f'(x)}$ podílem ${\displaystyle {\frac {f(x+h)-f(x-h)}{2h}}}$ je chyba srovnatelná s druhou mocninou hodnoty ${\displaystyle h}$. Tato aproximace je přesnější, než použití dopředné diference $${\displaystyle {\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 ${\displaystyle h}$. V praxi totiž bývá hodnota ${\displaystyle h}$ blízká k nule a tam druhá mocnina ubývá rychleji, například pro ${\displaystyle h=0.01}$ je ${\displaystyle h^{2}=0.0001}$, což dává dvojnásobný počet desetinných míst.^[zdroj?]

Odkazy

Reference

Externí odkazy

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

Zdroj