Landauova notace

Z Wikipedie, otevřené encyklopedie
Skočit na navigaci Skočit na vyhledávání

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?]

Formální definice[editovat | editovat zdroj]

Nechť a jsou dvě funkce definované na nějaké podmnožině reálných čísel. Potom lze říci, že

právě tehdy když

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]


Příklad[editovat | editovat zdroj]

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[editovat | editovat zdroj]

Reference[editovat | editovat zdroj]

  1. KUČERA, Luděk. Kombinatorické algoritmy. 2. vyd. Praha: SNTL, 1989. 
  2. KUČERA, Luděk. Combinatorial Algorithms. Bristol, England; New York, USA: Adam Hilger, 1989. Dostupné online. ISBN 0-85274-298-3. 

Externí odkazy[editovat | editovat zdroj]