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.
platí
n
n
≤
)
(
log
2
pro n = 1,2,…
Úlohy této třídy považujeme z časového hlediska za řešitelné. Jinak řečeno čas pro provedení
algoritmů považujeme obecně za přijatelný, ačkoliv už u kvadratického polynomu je pro větší
počty údajů čas potřebný pro výpočet dosti citelný. Všechny základní algoritmy obsažené
v tomto studijním textu patří do této třídy.
Poslední složitost v tabulce je vyjádřena exponenciální funkcí. Je zřejmé, že hodnota této funkce
roste tak drasticky, že i pro poměrně malé počty údajů je potřebný čas tak velký, že je nemožné
takovými algoritmy provést výpočet. Tyto algoritmy patří do třídy algoritmů s nepolynomiální
časovou složitostí. Mají tu vlastnost, že funkci jejich časové složitosti nelze shora ohraničit
žádným polynomem. Algoritmy této třídy považujeme za neřešitelné v přijatelném čase.
Existuje řada praktických úloh, které vedou k algoritmům této třídy. Zejména sem patří úlohy
na matematických grafech. Nemožnost tyto praktické úlohy řešit výpočtem algoritmů této třídy
se v praxi řeší sestavením algoritmů s přijatelnou (polynomickou) časovou složitostí pro tyto
úlohy, které neřeší danou úlohu přesně, ale jen přibližně, čímž typicky dávají o něco horší
výsledky, než by dal přesný algoritmus s nepolynomickou časovou složitostí.
Průvodce studiem
Skutečnost, že algoritmy pro řešení některých úloh mají exponenciální časovou
složitost, nám komplikuje život. Prakticky se použít nedají, musíme pro ně hledat
náhradní, přibližné algoritmy. Obecně je to tedy nepříznivý jev. Má to ale i jednu kladnou
stránku – tyto algoritmy lze velmi efektivně využít k ochraně informací pomocí šifrování.