Landauova notace

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledá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.

Formální definice[editovat | editovat zdroj]

Nechť a jsou dvě funkce definované na nějaké podmnožině reálných čísel. Potom řekneme, ž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]

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]


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. ISBN 0-85274-298-3.  

Externí odkazy[editovat | editovat zdroj]