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.
∞
+
=
+∞
→
)
(
)
(
lim
n
g
n
f
n
bude mít lepší časovou složitost druhý algoritmus.
Přejděme nyní k vlastnímu časovému odhadu. Čas potřebný pro výpočet jedné základní
operace algoritmu bude záviset na tom, jak je tato operace komplikovaná. V přeloženém
programu operace reprezentuje určitý počet strojových instrukcí a čím je operace
komplikovanější, tím více strojových instrukcí v přeloženém programu zahrnuje a tím
také delší bude doba jejího výpočtu. Uvážíme-li, že taktovací kmitočet dnešních
procesorů je řádově v GHz, můžeme předpokládat, že se provede 10 milionů základních
operací algoritmu za vteřinu (zopakujme, že zde mluvíme o operacích algoritmu, ne o
operacích procesoru). Tento odhad je dostatečně konzervativní (opatrný) na to, aby
reálně odpovídal většině algoritmů, které budou v tomto studijním materiálu probrány.
Následující tabulka ukazuje potřebný čas pro různé časové složitosti a různé počty
údajů, které algoritmem zpracováváme. Časy jsou pro přehlednost zaokrouhleny.
Počty údajů
Složitost
10
100
1 000
10 000
100 000 1 000 000
log2(n)
0.3 μs 0.7 μs
1 μs
1.3 μs
1.6 μs
2 μs
n
1 μs
10 μs
100 μs
1 ms
10 ms
100 ms
nlog2(n) 3 μs
67 μs
1 ms
13 ms
166 ms
2 s
Časovou
složitost
používáme
k odhadu doby
výpočtu.
− 7 −
n2
10 μs
1 ms
100 ms
10 s
17 min.
28 hod.
2n
102 μs 4.1015 roků
Algoritmy, jímž odpovídají první čtyři složitosti v tabulce, patří mezi algoritmy s polynomickou
časovou složitostí. Třída těchto algoritmů zahrnuje všechny algoritmy, jejich časová složitost je
přímo vyjádřena polynomem anebo pro jejich funkci časové složitosti existuje polynom, který ji
shora ohraničuje. Například pro funkci log2(n) je tímto polynomem lineární polynom neboť