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.
Vyjadřovat časovou složitost přímo v časových jednotkách by bylo velmi obtížné a rovněž i
problematické. Například vezměme zcela jednoduchou úlohu, kdy máme vypočítat součet n
čísel. Zřejmě bychom postupovali tak, že bychom vzali první číslo a k němu postupně přičítali
2., 3. až n-té číslo. Celkově bychom udělali n-1 operací přičtení. Pokud bychom to dělali ručně,
pak by celkový čas byl n-1 násobkem času, který potřebujeme pro přičtení jednoho čísla.
Jestliže to ale budeme dělat pomocí programu, bude určení času potřebného pro přičtení
jednoho čísla obtížné. Neboť program většinou píšeme v nějakém programovacím jazyce. Jak
dlouho v něm bude trvat přičtení jednoho čísla, přímo nevíme. Přesněji řečeno je to značně
obtížné určit, neboť program je před výpočtem nejdříve přeložen do jazyka procesoru, což
znamená, že bychom museli časovou složitost počítat ze strojových instrukcí přeloženého
programu. To ale bohužel není nijak jednoduché. Navíc doba výpočtu bude zřejmě také záviset
na tom, jak rychlý počítač pro výpočet použijeme. Abychom tyto nepříjemné aspekty
eliminovali, počítáme časovou složitost nikoliv v časových jednotkách, ale v počtech základních
Časová složitost
algoritmu je
významnější než
jeho paměťová
složitost.
Časová složitost
se vyjadřuje ne
v časových
jednotkách, ale
pomocí
základních
operací
algoritmu.