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 $𝒪(h^2)$, znamená to, že rychlost jejího růstu je shora omezena rychlostí růstu kvadratické funkce (neroste rychleji). Při pohledu na chování v okolí počátku, funkční hodnoty funkce z množiny $𝒪(h^2)$ se blíží k nule rychleji, než je tomu u lineární funkce.Šablona: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 𝒪(g(x))$

právě tehdy když

$\mathrm{\exists }(C>0),x_0:\mathrm{\forall }(x>x_0)|f(x)|\le |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 𝒪(g(x))$	$f$ je asymptoticky ohraničena funkcí $g$ shora (až na konstantu)	$\mathrm{\exists }(C>0),x_0:\mathrm{\forall }(x>x_0)|f(x)|\le |Cg(x)|$
$f(x)\in \mathrm{\Omega }(g(x))$	$f$ je asymptoticky ohraničena funkcí $g$ zdola (až na konstantu)	$\mathrm{\exists }(C>0),x_0:\mathrm{\forall }(x>x_0)|Cg(x)|\le |f(x)|$
$f(x)\in \mathrm{\Theta }(g(x))$	$f$ je asymptoticky ohraničena funkcí $g$ z obou stran (až na konstantu)	$\mathrm{\exists }(C,C^{\prime }>0),x_0:\mathrm{\forall }(x>x_0)|Cg(x)|<|f(x)|<|C^{\prime }g(x)|$
$f(x)\in o(g(x))$	$f$ je asymptoticky ohraničena funkcí $g$ shora ostře	$\mathrm{\forall }(C>0),\mathrm{\exists }{x}_0:\mathrm{\forall }(x>x_0)|f(x)|<|Cg(x)|$
$f(x)\in \omega (g(x))$	$f$ je asymptoticky ohraničena funkcí $g$ zdola ostře	$\mathrm{\forall }(C>0),\mathrm{\exists }{x}_0:\mathrm{\forall }(x>x_0)|Cg(x)|<|f(x)|$
$f(x)\sim g(x)$	asymptoticky rovné	$\underset{x\to \mathrm{\infty }}{\lim }\frac{f(x)}{g(x)}=1$

Vztahy mezi množinami

$\mathrm{\Theta }(g(x))=𝒪(g(x))\cap \mathrm{\Omega }(g(x))$

Příklad

Aproximace derivace pomocí centrální diference vzorcem $$\frac{\mathrm{d}f}{\mathrm{d}x}=f^{\prime }(x)=\frac{f(x+h)-f(x-h)}{2h}+𝒪(h^2)$$ukazuje, že při nahrazení derivace $f^{\prime }(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^{\prime }(x)=\frac{f(x+h)-f(x)}{h}+𝒪(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.Šablona:Zdroj?

Odkazy

Externí odkazy

• Odhady složitosti Šablona:Wayback Šablona:Cs