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 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 se blíží k nule rychleji, než je tomu u lineární funkce.
Formální definice
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.
Definici je možné modifikovat pro popis asymptotického chování v nule namísto nekonečna.
Další používané notace
NotaceVýznamDefinice 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řeasymptoticky rovné
Vztahy mezi množinami
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.
Odkazy
Reference
Externí odkazy
Odhady složitosti
Kategorie:Matematické zápisy Kategorie:Asymptotické chování