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.
ln(
)
(ln(
lim
)
2
ln(
)
ln(
lim
)
(
log
lim
n
n
n
n
n
n
n
n
n
n
n
n
0
1
lim
)
2
ln(
2
1
1
lim
)
2
ln(
2
=
∗
=
∗
+∞
→
+∞
→
n
n
n
n
n
Tedy první algoritmus má lepší časovou složitost a bude proto při výpočtu obecně
rychlejší.
2. Nejprve ověříme možnost a). Vypočítáme limitu podílu výchozí časové složitosti a
složitosti uvedené v možnosti a):
=
+
∗
=
+
=
+
+∞
→
+∞
→
+∞
→
)
ln(
1
)
2
ln(
)
ln(
2
lim
)
ln(
1
)
(
log
2
lim
)
ln(
1
)
(
log
lim
2
2
2
n
n
n
n
n
n
n
n
n
n
n
n
n
n
n
)
2
ln(
2
)
ln(
1
lim
)
2
ln(
2
)
ln(
1
)
2
ln(
2
lim
=
+
=
⎟⎟
⎠
⎞
⎜⎜
⎝
⎛
+
+∞
→
+∞
→
n
n
n
n
n
n
a b = log (n) / log (a)
b
b
/
/
/
/
/
/
/
/
/
− 9 −
Limita je konečná a nenulová, možnost a) je správně. Obdobný způsobem bychom
zjistili, že i možnost b) je správně. To víceméně ukazuje, že hodnota základu logaritmu
nemá vliv na míru složitosti.
Zbývá možnost c). Opět vypočítáme limitu podílu:
∞
+
=
=
⎟
⎠
⎞
⎜
⎝
⎛
+
=
+
+∞
→
+∞
→
+∞
→
)
(
log
lim
1
)
(
log
lim
1
)
(
log
lim
2
2
2
2
2
2
n
n
n
n
n
n
n
n
n
Z ní plyne, že odpověď c) je chybná. Protože hodnota limity podílu je
∞
+ , je míra
složitosti algoritmu větší než je míra složitosti lineární funkce n uvedené v možnosti c).
− 10 −
2 Datové struktury
Údaje, se kterými algoritmy pracují, mohou být jednak samostatné hodnoty nebo to mohou být
strukturované údaje. Samostatné hodnoty jsou tvořeny jednoduchými datovými typy, jako jsou
celá čísla, čísla v pohyblivé řádové čárce, řetězce atd. Strukturované údaje mají charakter
záznamů. Záznamy většinou popisují nějaké objekty. Je v nich více položek – datových členů,
přičemž každý člen popisuje nějaký rys nebo hodnotu daného objektu. Například bude-li
záznam popisovat osobu, pak typicky bude obsahovat její rodné číslo, jméno a příjmení,
jednotlivé části adresy bydliště (název ulice s popisným číslem, PSČ a název města) atd. Pro
popis algoritmů většinou není důležité, pro jaké datové typy budou prakticky použity, zda pro
jednoduché nebo pro strukturované datové typy. Budou pracovat s nějakými prvky z nějaké
množiny dat. Nicméně aby algoritmy mohly prvky vyhledávat nebo je srovnávat, potřebují, aby
u každého prvku byla stanovena hodnota, která ho reprezentuje. U prvků, jež jsou tvořeny
jednoduchými datovými typy, je touto hodnotou samotná hodnota prvku. U strukturovaného
typu je touto hodnotou většinou nějaký jeho člen (nebo několik jeho členů), a to takový, že jeho
hodnota prvek jednoznačně určuje. Hodnotě, která prvek reprezentuje (určuje), budeme říkat
klíč prvku.