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.
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é
|
|
![{\displaystyle \Theta (g(x))={\mathcal {O}}(g(x))\cap \Omega (g(x))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7a92177d94061243cc2723e7ada80d7a5ed000cd)
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})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a552dac91c4635456a7caa98dffc131b1da90d7c)
ukazuje, že při nahrazení derivace
![{\displaystyle f'(x)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d0cd7d7c75340e779d82658e19d1720ce84ab127)
podílem
![{\displaystyle {\frac {f(x+h)-f(x-h)}{2h}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/819b7ca1d76021add341038d5813fdea57030282)
je chyba srovnatelná s druhou mocninou hodnoty
![{\displaystyle h}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b26be3e694314bc90c3215047e4a2010c6ee184a)
. 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),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/52c1dbf50097c1e55d3d942ae4101e66b997db80)
kde je chyba srovnatelná "pouze" s první mocninou hodnoty
![{\displaystyle h}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b26be3e694314bc90c3215047e4a2010c6ee184a)
. V praxi totiž bývá hodnota
![{\displaystyle h}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b26be3e694314bc90c3215047e4a2010c6ee184a)
blízká k nule a tam
druhá mocnina ubývá rychleji, například pro
![{\displaystyle h=0.01}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e3b5fcea34e4ddc9e9c4643cf9aaf605c631b0e3)
je
![{\displaystyle h^{2}=0.0001}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3689687da39b68dbabe23a6b54fa22b823754ff4)
, což dává dvojnásobný počet desetinných míst.
[zdroj?]
- ↑ 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.