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
, 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
. Při pohledu na chování v okolí počátku, funkční hodnoty funkce z množiny
se blíží k nule rychleji, než je tomu u lineární funkce.[zdroj?]
Nechť
a
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))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c86dbff0afe14e26f135bb15e0c588ca2af9cbf5)
právě tehdy když
![{\displaystyle \exists (C>0),x_{0}:\forall (x>x_{0})\;|f(x)|\leq |Cg(x)|}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8faaebb42c3bebf498e07f1d93dccf2d609e4fff)
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 |
| je asymptoticky ohraničena funkcí shora (až na konstantu) | |
| je asymptoticky ohraničena funkcí zdola (až na konstantu) | |
| je asymptoticky ohraničena funkcí z obou stran (až na konstantu) | |
| je asymptoticky ohraničena funkcí shora ostře | |
| je asymptoticky ohraničena funkcí zdola ostře | |
| asymptoticky rovné | |
Vztahy mezi množinami
![{\displaystyle \Theta (g(x))={\mathcal {O}}(g(x))\cap \Omega (g(x))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7a92177d94061243cc2723e7ada80d7a5ed000cd)
Příklad
Aproximace derivace pomocí centrální diference vzorcem
ukazuje, že při nahrazení derivace
podílem
je chyba srovnatelná s druhou mocninou hodnoty
. Tato aproximace je přesnější, než použití dopředné diference
kde je chyba srovnatelná "pouze" s první mocninou hodnoty
. V praxi totiž bývá hodnota
blízká k nule a tam druhá mocnina ubývá rychleji, například pro
je
, což dává dvojnásobný počet desetinných míst.[zdroj?]
Odkazy
Reference
- ↑ KUČERA, Luděk. Kombinatorické algoritmy. 2. vyd. Praha: SNTL, 1989.
- ↑ KUČERA, Luděk. Combinatorial Algorithms. Bristol, England; New York, USA: Adam Hilger, 1989. Dostupné online. ISBN 0-85274-298-3.
Externí odkazy
- Odhady složitosti Archivováno 24. 2. 2016 na Wayback Machine. (česky)