Exponentiell komplexitet

Exponentiell komplexitet - i teorin om komplexitet av algoritmer , komplexiteten av problemet, begränsad av exponentialen av polynomet av dimensionen av problemet, det vill säga, det begränsas av funktionen , där är något polynom, och är storleken av problemet. I det här fallet sägs problemets komplexitet öka exponentiellt . Ofta hänvisar komplexitet till exekveringstiden för en algoritm. I det här fallet sägs algoritmen tillhöra klassen EXPTIME . Komplexitet kan dock också referera till minne eller andra resurser som behövs för att algoritmen ska fungera. $\exp(P(n))$ $P$ $n$

Skillnaden mellan polynomiska och exponentiella algoritmer går tillbaka till von Neumann . [ett]

Tidskomplexitet

Uppgifter med exponentiell körtidskomplexitet bildar klassen EXPTIME , formellt definierad som:

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

var är uppsättningen av problem som kan lösas av algoritmer vars körtid begränsas uppifrån av funktionen . $TID(f(n))$ $med)$

Jämförelse med polynom komplexitet

Det är allmänt accepterat att algoritmer med polynom komplexitet är "snabba", medan algoritmer med mer än polynom komplexitet är "långsamma". Ur denna synvinkel är algoritmer med exponentiell komplexitet långsamma. Detta antagande är dock inte helt korrekt. Faktum är att algoritmens gångtid beror på värdet av n (dimensionen av problemet) och relaterade konstanter dolda i O-notationen . I vissa fall, för små värden på n , kan polynomtiden överstiga exponentiell tid. Men för stora värden på n är körtiden för algoritmen med exponentiell komplexitet mycket längre.

Subexponentiell komplexitet

Det finns algoritmer som körs på mer än polynomtid ( "superpolynom" ), men mindre än exponentiell tid ( "subexponentiell" ). Ett exempel på ett sådant problem är faktorisering av ett heltal i primtalsfaktorer ( faktorisering ). Sådana algoritmer kallas också "långsamma".

Se även

EXPTIME klass
O notation
konstant tid
Linjär tid
NP komplett problem

Anteckningar

↑ John von Neumann. Ett visst nollsummespel för två personer som motsvarar det optimala uppdragsproblemet // Contributions to the Theory of Games / HW Kuhn , AW Tucker , Eds. — Princeton, NJ: Princeton Univ. Press , 1953. - S. 5-12. — 404 sid.