BPC-ALD - Skripta_rev2019_2

4.4

Hašování (Transformace klíče) ........................................................................................................81

4.4.1

Otevřené adresování .................................................................................................................83

4.4.2

Zřetězení...................................................................................................................................87

5

Rejstřík .....................................................................................................................................................91

− 4 − 

1  Algoritmus 

Algoritmus je popis určitého postupu. Příkladem algoritmu by mohl být recept na přípravu jídla 
obsažený  v kuchařské  knize.  My  se  zde  přirozeně  nebudeme  zabývat  algoritmy  vaření,  ale 
postupy některých často používaných výpočtů. Pojem výpočet mnohdy vytváří asociaci, že jde 
o výpočet číselné povahy. Zde je tento pojem použit v širším slova smyslu, označuje zde nějaké 
zpracování údajů. Typ těchto údajů může být různý, mohou to být jak čísla, tak i textové řetězce 
apod. 

Průvodce studiem  

Algoritmy prolínají celý náš život. Ovšem běžně se jim neříká algoritmy, ale návody, 

pokyny k používání atd. Užitečnost a význam algoritmů oceníme zejména, když se snažíme 
sami přijít na to, jak se s novou věcí zachází. Často  po delší době neúspěchů nakonec 
rezignujeme a přečteme si přiložený návod. 

1.1  Složitost algoritmu 

Studijní cíle:  Zavést a vysvětlit pojem časové složitosti algoritmu a objasnit její důležitost pro 
výběr konkrétního algoritmu. 

Klíčová slova: Paměťová složitost, časová složitost, polynomická složitost. 

Potřebný čas: 1 hodina 

Výrazným rysem algoritmů je jejich složitost. Vraťme se k našemu původnímu příkladu receptu 
na  přípravu  jídla.  Bude  záležet  na  tom,  pro  kolik  osob  jídlo  budeme  připravovat.  Čím  více 
těchto  osob  bude,  tím  jednak  budeme  potřebovat  větší  nádobí  a  dále  nám  typicky  bude  i 
příprava jídla trvat déle. Budeme třeba muset oškrábat více brambor atd. Stejně tak při výpočtu 
čím  více  údajů  budeme  zpracovávat,  tím  větší  množství  paměti  budeme  potřebovat  pro  jejich 
uložení  a  rovněž  čas  výpočtu  bude  delší.  Závislost  velikosti  paměti  potřebné  pro  výpočet  na 
počtu zpracovávaných údajů nazýváme paměťovou složitostí algoritmu. Závislost doby výpočtu 
na  počtu  zpracovávaných  údajů  nazýváme časovou  složitostí  algoritmu.  My  se  u  jednotlivých 
algoritmů budeme zabývat jen jejich časovou složitostí. Paměťová složitost přirozeně má také 
svůj význam. Nicméně při současných velikostech pamětí počítačů nebývá u většiny algoritmů 
omezujícím faktorem pro jejich použití a není tudíž pro nás tak důležitá jako časová složitost.