Z Wikipedie, otevřené encyklopedie
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
O
(
h
2
)
{\displaystyle {\mathcal {O}}(h^{2})}
O
(
h
)
{\displaystyle {\mathcal {O}}(h)}
O
(
h
2
)
{\displaystyle {\mathcal {O}}(h^{2})}
[zdroj?
Nechť
f
(
x
)
{\displaystyle f(x)}
g
(
x
)
{\displaystyle g(x)}
reálných čísel . Potom lze říci, že
f
(
x
)
∈
O
(
g
(
x
)
)
{\displaystyle f(x)\in {\mathcal {O}}(g(x))}
právě tehdy když
∃
(
C
>
0
)
,
x
0
:
∀
(
x
>
x
0
)
|
f
(
x
)
|
≤
|
C
g
(
x
)
|
{\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.
Notace
Význam
Definice
f
(
x
)
∈
O
(
g
(
x
)
)
{\displaystyle f(x)\in {\mathcal {O}}(g(x))}
f
{\displaystyle f}
g
{\displaystyle g}
∃
(
C
>
0
)
,
x
0
:
∀
(
x
>
x
0
)
|
f
(
x
)
|
≤
|
C
g
(
x
)
|
{\displaystyle \exists (C>0),x_{0}:\forall (x>x_{0})\;|f(x)|\leq |Cg(x)|}
f
(
x
)
∈
Ω
(
g
(
x
)
)
{\displaystyle f(x)\in \Omega (g(x))}
f
{\displaystyle f}
g
{\displaystyle g}
∃
(
C
>
0
)
,
x
0
:
∀
(
x
>
x
0
)
|
C
g
(
x
)
|
≤
|
f
(
x
)
|
{\displaystyle \exists (C>0),x_{0}:\forall (x>x_{0})\;|Cg(x)|\leq |f(x)|}
f
(
x
)
∈
Θ
(
g
(
x
)
)
{\displaystyle f(x)\in \Theta (g(x))}
f
{\displaystyle f}
g
{\displaystyle g}
∃
(
C
,
C
′
>
0
)
,
x
0
:
∀
(
x
>
x
0
)
|
C
g
(
x
)
|
<
|
f
(
x
)
|
<
|
C
′
g
(
x
)
|
{\displaystyle \exists (C,C'>0),x_{0}:\forall (x>x_{0})\;|Cg(x)|<|f(x)|<|C'g(x)|}
f
(
x
)
∈
o
(
g
(
x
)
)
{\displaystyle f(x)\in o(g(x))}
f
{\displaystyle f}
g
{\displaystyle g}
∀
(
C
>
0
)
,
∃
x
0
:
∀
(
x
>
x
0
)
|
f
(
x
)
|
<
|
C
g
(
x
)
|
{\displaystyle \forall (C>0),\exists x_{0}:\forall (x>x_{0})\;|f(x)|<|Cg(x)|}
f
(
x
)
∈
ω
(
g
(
x
)
)
{\displaystyle f(x)\in \omega (g(x))}
f
{\displaystyle f}
g
{\displaystyle g}
∀
(
C
>
0
)
,
∃
x
0
:
∀
(
x
>
x
0
)
|
C
g
(
x
)
|
<
|
f
(
x
)
|
{\displaystyle \forall (C>0),\exists x_{0}:\forall (x>x_{0})\;|Cg(x)|<|f(x)|}
f
(
x
)
∼
g
(
x
)
{\displaystyle f(x)~\sim g(x)}
asymptoticky rovné
lim
x
→
∞
f
(
x
)
g
(
x
)
=
1
{\displaystyle \lim _{x\to \infty }{\frac {f(x)}{g(x)}}=1}
Θ
(
g
(
x
)
)
=
O
(
g
(
x
)
)
∩
Ω
(
g
(
x
)
)
{\displaystyle \Theta (g(x))={\mathcal {O}}(g(x))\cap \Omega (g(x))}
Aproximace derivace pomocí centrální diference vzorcem
d
f
d
x
=
f
′
(
x
)
=
f
(
x
+
h
)
−
f
(
x
−
h
)
2
h
+
O
(
h
2
)
{\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
f
′
(
x
)
{\displaystyle f'(x)}
podílem
f
(
x
+
h
)
−
f
(
x
−
h
)
2
h
{\displaystyle {\frac {f(x+h)-f(x-h)}{2h}}}
je chyba srovnatelná s druhou mocninou hodnoty
h
{\displaystyle h}
. Tato aproximace je přesnější, než použití
dopředné diference
d
f
d
x
=
f
′
(
x
)
=
f
(
x
+
h
)
−
f
(
x
)
h
+
O
(
h
)
,
{\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
h
{\displaystyle h}
. V praxi totiž bývá hodnota
h
{\displaystyle h}
blízká k nule a tam druhá mocnina ubývá rychleji, například pro
h
=
0.01
{\displaystyle h=0.01}
je
h
2
=
0.0001
{\displaystyle h^{2}=0.0001}
, což dává dvojnásobný počet desetinných míst.
[zdroj?
↑ 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 
