BPC-ALD - Skripta_rev2019_2
Níže je uveden pouze náhled materiálu. Kliknutím na tlačítko 'Stáhnout soubor' stáhnete kompletní formátovaný materiál ve formátu PDF.
Θ, který vyjadřuje, že funkce
v něm uvedená má stejnou míru složitosti jako funkce, jež je přesným vyjádřením časové
složitosti algoritmu. Tj. místo abychom psali, že algoritmus má časovou složitost
3
4
2
+
− n
n
,
napíšeme jen, že jeho časová složitost je
)
( 2
n
Θ
.
Matematicky skutečnost, že dvě funkce časové složitosti mají stejnou míru nárůstu hodnoty,
můžeme charakterizovat tak, že jejich poměr (podíl) konverguje ke konečné nenulové hodnotě
pro rostoucí argument n. Je-li tedy časová složitost algoritmu dána funkcí f(n) a dále máme
funkci g(n) takovou, že je splněno
∞
+
<
<
+∞
→
)
(
)
(
lim
0
n
g
n
f
n
pak můžeme napsat, že časová složitost algoritmu je
))
(
( n
g
Θ
.
Jiný možný způsob, jak funkci g(n) definovat, je, že musí existovat dvě kladná nenulová čísla c1
a c2 a přirozené číslo n0 taková, že platí
− 6 −
)
(
.
)
(
)
(
.
2
1
n
g
c
n
f
n
g
c
≤
≤
pro
0
n
n
≥ .
Uvedený vztah je znázorněn na následujícím obrázku.
Například v již uvedeném příkladu je limita podílu vlastní funkce časové složitosti algoritmu a
funkce n2:
4
1
3
4
1
lim
2
2
=
+
−
+∞
→
n
n
n
n
.
Pomocí limity můžeme také charakterizovat, kdy je časová složitost jednoho algoritmu lepší ve
srovnání s druhým algoritmem. Mějme dva algoritmy a nechť první má časovou složitost
vyjádřenou funkcí f(n) a druhý má časovou složitost g(n). Jestliže bude platit
0
)
(
)
(
lim
=
+∞
→
n
g
n
f
n
pak zřejmě funkce f(n) roste pomaleji než funkce g(n) a tudíž první algoritmus bude mít lepší
časovou složitost. Naopak bude-li platit