Exponenciális komplexitás

Exponenciális komplexitás - az algoritmusok bonyolultságának elméletében a probléma összetettsége, amelyet a probléma dimenziójának polinomjának exponenciálisa korlátoz , vagyis korlátozza a függvény , ahol valamilyen polinom, és a mérete a problémáról. Ebben az esetben a probléma összetettsége exponenciálisan növekszik . A bonyolultság gyakran egy algoritmus végrehajtási idejére utal. Ebben az esetben azt mondjuk, hogy az algoritmus az EXPTIME osztályba tartozik . A komplexitás azonban utalhat a memóriára vagy az algoritmus működéséhez szükséges egyéb erőforrásokra is. $\exp(P(n))$ $P$ $n$

A polinomiális és az exponenciális algoritmusok megkülönböztetése Neumannig nyúlik vissza . [egy]

Időbonyolultság

Az exponenciális futásidejű bonyolultságú feladatok az EXPTIME osztályt alkotják , amely formálisan a következőképpen van meghatározva:

{\text{EXPTIME}}=\bigcup _{k=1}^{\infty }TIME\left(2^{n^{k}}\right)

ahol az olyan algoritmusokkal megoldható feladatok halmaza, amelyek futási idejét felülről a függvény határolja . $IDŐ(f(n))$ $f(t)$

Összehasonlítás polinomiális komplexitással

Általánosan elfogadott, hogy a polinomiális komplexitású algoritmusok "gyorsak", míg a polinomnál nagyobb bonyolultságú algoritmusok "lassúak". Ebből a szempontból az exponenciális bonyolultságú algoritmusok lassúak. Ez a feltételezés azonban nem teljesen pontos. Az a tény, hogy az algoritmus futási ideje függ n értékétől (a probléma dimenziója) és az O-jelölésben elrejtett kapcsolódó konstansoktól . Egyes esetekben kis n értékek esetén a polinomiális idő meghaladhatja az exponenciális időt. Nagy n értékek esetén azonban az exponenciális bonyolultságú algoritmus futási ideje sokkal hosszabb.

Szubexponenciális komplexitás

Vannak olyan algoritmusok, amelyek több mint polinomiális időben futnak ( "szuperpolinom" ), de exponenciálisnál rövidebb idő alatt ( "szub-exponenciális" ). Ilyen probléma például az egész szám prímtényezőkké alakítása ( faktorizáció ) . Az ilyen algoritmusokat "lassúnak" is nevezik.

Lásd még

EXPTIME osztály
O jelölés
állandó idő
Lineáris idő
NP teljes probléma

Jegyzetek

↑ Neumann János. Egy bizonyos nulla összegű kétszemélyes játék, amely megfelel az optimális hozzárendelési problémának // Contributions to the Theory of Games / HW Kuhn , AW Tucker , szerk. – Princeton, NJ: Princeton Univ. Press , 1953. - P. 5-12. — 404 p.