Landauova notace
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
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
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
Příklad editovat
Aproximace derivace pomocí centrální diference vzorcem
Odkazy editovat
Reference editovat
- ↑ 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 editovat
- Odhady složitosti Archivováno 24. 2. 2016 na Wayback Machine. (česky)