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.
Kontrolní otázky
1. Jakým způsobem vyjadřujeme časovou složitost algoritmu?
2. Vysvětlete, jaký je základní rozdíl z pohledu prakticky využitelnosti mezi algoritmy
s polynomickou časovou složitostí a algoritmy s nepolynomickou časovou složitostí.
Cvičení
1. Pro řešení úlohy máme dva algoritmy, jejichž časové složitosti jsou
a)
)
(
log
2 n
b)
n
Který z nich je rychlejší, tj. má příznivější časovou složitost?
2. Pro daný algoritmus jsem odvodili, že jeho časová složitost je dána funkcí
1
)
(
log
2
2
+
n
n
Když o tomto algoritmu napíšeme, že jeho časová složitost je
Za prakticky
použitelné
obecně
považujeme
algoritmy
s polynomickou
časovou
složitostí.
− 8 −
1.
))
ln(
(
n
n
Θ
(ln označuje přirozený logaritmus)
2.
))
(
log
(
10 n
n
Θ
3.
)
(n
Θ
které z těchto možností jsou správně?
Úkoly k textu
Představme si, že škrábeme brambory na přípravu oběda pro děti v letním táboře. Základní
operací zde bude oškrábání jednoho bramboru. Nechť počet škrábaných brambor pro jeden oběd
je 5. Stanovte, jaká je časová složitost algoritmu, je-li počet dětí na táboře n.
Jak se změní míra časové složitosti, když
- Brambory nebudu škrábat sám, ale budeme to dělat dva
- Každé dítě si samo oškrábe brambory na svůj oběd
Řešení
1. Který algoritmus je rychlejší, stanovíme podle limity podílu jejich časových složitostí.
Vzhledem k tomu, že obě funkce časových složitostí neomezeně rostou, vede to k limitě
výrazu typu
∞
+
∞
+
. Pro výpočet použijeme l’Hospitalovo pravidlo
)
(
'
)
(
'
lim
)
(
)
(
lim
n
g
n
f
n
g
n
f
n
n
+∞
→
+∞
→
=
Dále pro logaritmus použijeme pravidlo, jež logaritmus o základu a převádí na
logaritmus o jiném základu b
)
(
log
)
(
log
)
(
log
a
n
n
b
b
a
∗
=
Nyní již můžeme limitu počítat
=
∗
=
∗
=
∗
=
−
+∞
→
+∞
→
+∞
→
+∞
→
2
1
2
1
2
1
2
2
1
)
2
ln(
1
lim
)'
(
))'
2