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.

Formální definiceEditovat

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é notaceEditovat

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žinamiEditovat

 

OdkazyEditovat

ReferenceEditovat

  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í odkazyEditovat