Wiki definerer Polynomial tid som brak:
En algoritme siges at have polynomisk tid, hvis dens driftstid er øvre afgrænset af et polynomisk udtryk i størrelsen af input for algoritmen, dvs. $ T (n) = O (n ^ k) $ for nogle konstante $ k $
I forstå, at generelt set er forskellen mellem Polynomial tid og Eksponentiel tid er, at den eksponentielle funktion vokser strengt hurtigere end nogen polynomial funktion, asymptotisk ( reference ).
Jeg prøver at forstå kernen definition af Eksponentiel tid .
- Hvilke elementer får en algoritme til at køre i Eksponentiel tid ?
- Hvilken ændring skal jeg gøre i polynomieudtryk at gøre det til Eksponentiel tid ? (Af it Jeg henviser til algoritmedefinitionen i starten af spørgsmålet)
Kommentarer
- 1. Gør eksponentielt mange ting. 2. Brug polynomet som styrken i en base > 1.
- Jeg forstår ikke ' for at forstå dit andet spørgsmål. Polynomer er polynomer; eksponentielle er eksponentielle. At spørge, hvad du har brug for at ændre for at gøre et polynom til en eksponentiel, er som at spørge, hvad du har brug for at ændre for at gøre en logaritme til en cosinus.
- @ DavidRicherby Vil der være eksponentielle tidsfunktioner, hvis P = NP? Hvordan kan du definere en eksponentiel tidsfunktion i form af polynomielt udtryk?
- Eksponentielle funktioner vil bestemt stadig eksistere, hvis P = NP. Der er sandsynligvis stadig problemer, der ' tager eksponentiel tid, selvom P = NP, selvom ingen kommer i tankerne med det samme. En eksponentiel funktion kan defineres i form af et polynom, men det polynom skal være uendeligt langt – du vil måske slå Taylor Expansions op, hvis du ' er interesseret i dette.
- @ymbirtt Selv den nemmeste version af tidshierarki sætning siger, at der ikke er nogen polynomial-tidsalgoritme til noget EXPTIME-komplet problem. At ' er et ubetinget resultat: det afhænger ikke ' af antagelsen om, at P $ \ neq $ NP.
Svar
-
Der er ikke noget let svar på denne, selvom der er tegn til at passe på Undersøgelse af alle mulige undersæt i et sæt er for eksempel eksponentiel – så hvis jeg havde et sæt heltal $ \ {x_1, …, x_n \} $, og ville kontrollere hver delmængde af disse for at se, om de summerer til $ 0 $, bliver jeg nødt til at overveje nøjagtigt $ 2 ^ n $ delmængder, hvilket gør denne metode eksponentiel tid. Flere forskellige fælder kan gøre en algoritme eksponentiel tid, men i stedet for at kigge efter brede kategorier, analyser algoritmer fra sag til sag.
-
Hvis en algoritme tager $ n ^ 2 $ trin for at fuldføre, er den polynom. Hvis det tager $ 2 ^ n $ trin, er den eksponentiel. Forskellen er placeringen af $ n $. Hvis noget er $ O (n ^ m) $ for $ n > 1 $, $ m > 0 $, så er det “s polynom i $ n $ for faste $ m $, men eksponentielt i $ m $ for faste $ n $.
Kommentarer
- Forsigtig. Funktionen $ n ^ m $ isn ' t polynom i $ n $ medmindre $ m $ er en konstant. Og hvis $ m $ er en konstant, det giver ' ikke mening at sige, at funktionen er eksponentiel i den konstante.
- Ja, du ' har ret. Jeg ' Jeg præciserer det.
Svar
Ofte får du en eksponentiel tidsbrute-force-algoritme, når du overvejer et problem, og tæller hele søgerummet. Typisk ville du tænke på delmængdeproblemer (i SAT vælger du et undersæt variabler indstillet til ægte), permutationsproblemer (i TSP er hver tur en permutation af byerne) og partitionsproblemer (i graffarvning prøver du at p opdele hjørnerne i farveklasser). Eller overvej at sortere selv: der er $ n! $ Permutationer på $ n $ heltal. Gå gennem hver permutation, og kontroller, om den er sorteret. Dumt (og langsomt), men det virker.
Kommentarer
- Selvom bemærk at $ O (n!) $ Er endnu værre end $ O ( k ^ n) $. Hvis du ' stadig prøver at lære om tidskompleksitet, kan dette være en nyttig ting at bevise for dig selv.