BPC-ALD - Skripta_rev2019_2

− 5 − 

operacích,  na  kterých  je  příslušný  algoritmus  založen.  V našem  příkladu  součtu  je  základní 
operací přičtení a časová složitost tohoto algoritmu je vyjádřena lineární funkcí n-1. 

Obecně  je  časová  složitost  vyjádřena  matematickými  funkcemi,  jejichž  argumentem  je  počet 
údajů, které zpracováváme. Velmi často tyto funkce jsou přímo polynomy, z ostatních funkcí se 
poměrně často vyskytuje logaritmická funkce. Např. 

3

4

2

+

− n

n

)

1

(

log

3

2

−

n

n

atd. 

Časová složitost nám sice neudává přímo čas výpočtu, ale dá se z ní odvodit, jak dlouho řádově 
bude výpočet pro náš počet údajů trvat (vteřiny, minuty, hodiny atd.). To nám stačí, abychom 
posoudili, zda daný algoritmus je pro nás použitelný. Dále je časová složitost důležitá v případě, 
kdy  máme pro danou úlohu  více  algoritmů a  máme  se  rozhodnout,  který z nich  použít. Často 
máme na jedné straně algoritmy, které jsou jednoduché, ale  mají větší časovou složitost, a na 
druhé  straně  máme  algoritmy  s příznivější  časovou  složitosti,  které  jsou  ale  komplikovanější, 
čímž  jejich  realizace,  tj.  naprogramování  je  obtížnější.  V tomto  případě  nám  pro  menší  počty 
údajů stačí jednodušší algoritmus, a máme-li hodně údajů, musíme zvolit sice pracnější, ale na 
druhé straně rychlejší algoritmus. 

Uvažujme nyní následující tři funkce: 

3

4

2

+

− n

n

4

2

n

2

n  

Ta  první  funkce  nechť  je  časovou  složitostí  nějakého  konkrétního  algoritmu.  Druhou  jsme 
dostali  zanedbáním  jejího  lineárního  a  absolutního  členu  a  v  třetí  jsme  navíc  odstranili 
koeficient u kvadratického členu. Všechny tři funkce jsou kvadratickým polynomem. Ta první 
vyjadřuje  odvozenou  složitost,  naproti  tomu  ta  poslední  je  z nich  nejjednodušší.  Vzhledem 
k tomu,  že  u  všech  jde  o  polynom  stejného  řádu,  mají  obdobný  nárůst  funkční  hodnoty  při 
rostoucím  počtu  údajů,  tj.  při  zvyšující  se  hodnotě  argumentu  n.  Už  jsme  uvedli,  že  časovou 
složitost  používáme  nikoliv  k přesnému  určení  doby  výpočtu,  ale  k jejímu  řádovému  odhadu. 
Pro tento účel nám místo první funkce, sice přesné, ale poměrně složité zcela vyhoví mnohem 
jednodušší poslední funkce n2. Pro tento účel se používá operátor