Exponenciální složitost

Exponenciální složitost - v teorii složitosti algoritmů je složitost problému omezená exponenciálou polynomu dimenze problému, to znamená, že je omezena funkcí , kde je nějaký polynom, a je velikost problému. V tomto případě se říká, že složitost problému roste exponenciálně . Složitost se často týká doby provádění algoritmu. V tomto případě se říká, že algoritmus patří do třídy EXPTIME . Složitost však může také odkazovat na paměť nebo jiné zdroje potřebné pro fungování algoritmu.

Rozdíl mezi polynomiálními a exponenciálními algoritmy sahá až k von Neumannovi . [jeden]

Časová složitost

Úlohy s exponenciální složitostí za běhu tvoří třídu EXPTIME , formálně definovanou jako:

,

kde je množina problémů, které lze řešit pomocí algoritmů, jejichž doba běhu je shora omezena funkcí .

Srovnání s polynomiální složitostí

Obecně se uznává, že algoritmy s polynomiální složitostí jsou „rychlé“, zatímco algoritmy s více než polynomiální složitostí jsou „pomalé“. Z tohoto pohledu jsou algoritmy s exponenciální složitostí pomalé. Tento předpoklad však není zcela přesný. Faktem je, že doba běhu algoritmu závisí na hodnotě n (rozměr problému) a souvisejících konstantách skrytých v O-notaci . V některých případech pro malé hodnoty n může polynomiální čas překročit exponenciální čas. Pro velké hodnoty n je však doba běhu algoritmu s exponenciální složitostí mnohem delší.

Subexponenciální složitost

Existují algoritmy, které běží ve více než polynomiálním čase ( „super-polynomiální“ ), ale v kratším než exponenciálním čase ( „sub-exponenciální“ ). Příkladem takového problému je rozklad celého čísla na prvočinitele ( faktorizace ) . Takové algoritmy jsou také označovány jako "pomalé".

Viz také

Poznámky

  1. ↑ John von Neumann. Jistá hra pro dvě osoby s nulovým součtem ekvivalentní problému optimálního zadání // Příspěvky k teorii her  / HW Kuhn , AW Tucker , Eds. — Princeton, NJ: Princeton Univ. Tisk , 1953. - S. 5-12. — 404 s.