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 ${\displaystyle {\mathcal {O}}(h^{2})}$, 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 ${\displaystyle {\mathcal {O}}(h)}$. Při pohledu na chování v okolí počátku, funkční hodnoty funkce z množiny ${\displaystyle {\mathcal {O}}(h^{2})}$ se blíží k nule rychleji, než je tomu u lineární funkce.^[zdroj?]

Nechť ${\displaystyle f(x)}$ a ${\displaystyle g(x)}$ jsou dvě funkce definované na nějaké podmnožině reálných čísel. Potom lze říci, že

${\displaystyle f(x)\in {\mathcal {O}}(g(x))}$

právě tehdy když

${\displaystyle \exists (C>0),x_{0}:\forall (x>x_{0})\;|f(x)|\leq |Cg(x)|}$

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.

${\displaystyle \Theta (g(x))={\mathcal {O}}(g(x))\cap \Omega (g(x))}$

Aproximace derivace pomocí centrální diference vzorcem $${\displaystyle {\frac {\mathrm {d} f}{\mathrm {d} x}}=f'(x)={\frac {f(x+h)-f(x-h)}{2h}}+{\mathcal {O}}(h^{2})}$$ukazuje, že při nahrazení derivace ${\displaystyle f'(x)}$ podílem ${\displaystyle {\frac {f(x+h)-f(x-h)}{2h}}}$ je chyba srovnatelná s druhou mocninou hodnoty ${\displaystyle h}$. Tato aproximace je přesnější, než použití dopředné diference $${\displaystyle {\frac {\mathrm {d} f}{\mathrm {d} x}}=f'(x)={\frac {f(x+h)-f(x)}{h}}+{\mathcal {O}}(h),}$$kde je chyba srovnatelná "pouze" s první mocninou hodnoty ${\displaystyle h}$. V praxi totiž bývá hodnota ${\displaystyle h}$ blízká k nule a tam druhá mocnina ubývá rychleji, například pro ${\displaystyle h=0.01}$ je ${\displaystyle h^{2}=0.0001}$, což dává dvojnásobný počet desetinných míst.^[zdroj?]

• Odhady složitosti Archivováno 24. 2. 2016 na Wayback Machine. (česky)