Cesko.wiki Landauova notace
Author
Albert FloresLandauova 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.
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) \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) |
| 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)~\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 dx}=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 dx}=f'(x)=\frac{f(x+h)-f(x)}{h}+\mathcal O(h),kde je chyba srovnatelná "pouze" s první mocninou hodnoty h. +more 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.
Odkazy
Reference
Externí odkazy
[url=http://wiki.matfyz.cz/index.php?title=St%C3%A1tnice_-_Odhady_slo%C5%BEitosti]Odhady složitosti[/url]