Eksponentiaalinen monimutkaisuus

Eksponentiaalinen monimutkaisuus - algoritmien monimutkaisuuden teoriassa ongelman monimutkaisuus, jota rajoittaa ongelman ulottuvuuden polynomin eksponentiaali , eli sitä rajoittaa funktio , jossa on jokin polynomi ja sen koko ongelmasta. Tässä tapauksessa ongelman monimutkaisuuden sanotaan kasvavan eksponentiaalisesti . Usein monimutkaisuus viittaa algoritmin suoritusaikaan. Tässä tapauksessa algoritmin sanotaan kuuluvan luokkaan EXPTIME . Monimutkaisuus voi kuitenkin viitata myös muistiin tai muihin algoritmin toimimiseen tarvittaviin resursseihin. $\exp(P(n))$ $P$ $n$

Ero polynomisten ja eksponentiaalisten algoritmien välillä juontaa juurensa von Neumannille . [yksi]

Aika monimutkaisuus

Tehtävät, joiden ajonaikainen monimutkaisuus on eksponentiaalinen, muodostavat luokan EXPTIME , joka on muodollisesti määritelty seuraavasti:

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

missä on joukko ongelmia, jotka voidaan ratkaista algoritmeilla, joiden ajoaika on ylhäältä funktion rajoittama . ${\näyttötyyli AIKA(f(n))}$ $f(t)$

Vertailu polynomin monimutkaisuuteen

On yleisesti hyväksyttyä, että algoritmit, joilla on polynomin monimutkaisuus , ovat "nopeita", kun taas algoritmit, joiden monimutkaisuus on enemmän kuin polynomi, ovat "hitaita". Tästä näkökulmasta katsottuna eksponentiaalisesti monimutkaiset algoritmit ovat hitaita. Tämä oletus ei kuitenkaan ole täysin oikea. Tosiasia on, että algoritmin ajoaika riippuu n:n arvosta ( tehtävän ulottuvuus) ja siihen liittyvistä O-merkinnässä piilotetuista vakioista . Joissakin tapauksissa pienillä n: n arvoilla polynomiaika voi ylittää eksponentiaalisen ajan. Kuitenkin suurilla n:n arvoilla eksponentiaalisesti monimutkaisen algoritmin ajoaika on paljon pidempi.

Subeksponentiaalinen monimutkaisuus

On algoritmeja, jotka toimivat enemmän kuin polynomiajassa ( "superpolynomi" ), mutta lyhyemmässä ajassa kuin eksponentiaalisessa ajassa ( "subeksponentiaalinen" ). Esimerkki tällaisesta ongelmasta on kokonaisluvun laskeminen alkutekijöiksi ( faktorointi ) . Tällaisia algoritmeja kutsutaan myös "hitaiksi".

Katso myös

EXPTIME-luokka
O merkintä
vakioaika
Lineaarinen aika
NP täydellinen ongelma

Muistiinpanot

↑ John von Neumann. Tietty nollasumman kahden hengen peli, joka vastaa optimaalista tehtäväntehtävää // Contributions to the Theory of Games / HW Kuhn , AW Tucker , toim. — Princeton, NJ: Princeton Univ. Press , 1953. - s. 5-12. — 404 s.