Wiki definieert Polynoomtijd als braak:
Van een algoritme wordt gezegd dat het een polynoomtijd heeft als de looptijd bovengrens is door een polynoomuitdrukking in de grootte van de invoer voor het algoritme, dwz $ T (n) = O (n ^ k) $ voor een constante $ k $
I begrijp dat in het algemeen het verschil tussen Polynoomtijd en Exponentiële tijd is dat exponentiële functie strikt sneller groeit dan welke polynoomfunctie dan ook, asymptotisch ( referentie ).
Ik probeer de kern te begrijpen definitie van Exponentiële tijd .
- Welke elementen zorgen ervoor dat een algoritme wordt uitgevoerd in Exponentiële tijd ?
- Welke wijziging moet ik aanbrengen in de veeltermuitdrukking om het Exponentiële tijd te maken? (Met het verwijs ik naar de algoritme-definitie in het begin van de vraag)
Opmerkingen
- 1. Doe exponentieel veel dingen. 2. Gebruik de polynoom als de kracht van een grondtal > 1.
- Ik begrijp ' je seconde niet vraag. Polynomen zijn polynomen; exponentials zijn exponentials. Vragen wat je moet veranderen om van een polynoom een exponentieel te maken, is als vragen wat je moet veranderen om van een logaritme een cosinus te maken.
- @DavidRicherby Zijn er exponentiële tijdfuncties als P = NP? Hoe kun je een exponentiële tijdfunctie definiëren in termen van polynoomuitdrukking?
- Exponentiële functies zullen zeker nog bestaan als P = NP. Er zijn waarschijnlijk nog steeds problemen die ' ll exponentieel duren, zelfs als P = NP, hoewel er niet meteen in me opkomt. Een exponentiële functie kan worden gedefinieerd in termen van een polynoom, maar die polynoom moet oneindig lang zijn – misschien wil je Taylor Expansions opzoeken als je ' hierin geïnteresseerd bent.
- @ymbirtt Zelfs de gemakkelijkste versie van de tijdhiërarchiestelling zegt dat er geen polynoom-tijd-algoritme is voor enig EXPTIME-compleet probleem. Dat ' is een onvoorwaardelijk resultaat: het is niet ' afhankelijk van de aanname dat P $ \ neq $ NP.
Antwoord
-
Er is geen gemakkelijk antwoord voor dit antwoord, hoewel er tekenen zijn om op te letten . Het onderzoeken van elke mogelijke subset van een set, bijvoorbeeld, is exponentieel – dus als ik een set van gehele getallen $ \ {x_1, …, x_n \} $ had, en ik elke subset hiervan wilde controleren om te zien of ze optellen tot $ 0 $, zou ik precies $ 2 ^ n $ subsets moeten overwegen, wat deze methode exponentieel maakt. Verschillende valstrikken kunnen een algoritme echter exponentieel maken, dus in plaats van te letten op brede categorieën, analyseer je algoritmen van geval tot geval.
-
Als een algoritme $ n ^ 2 $ stappen nodig heeft om te voltooien, dan is het polynoom. Als het $ 2 ^ n $ stappen kost, is het exponentieel. Het verschil is de positie van de $ n $. Als iets $ O (n ^ m) $ for $ n > 1 $, $ m > 0 $ is, dan is het polynoom in $ n $ voor vast $ m $, maar exponentieel in $ m $ voor vast $ n $.
Commentaar
- Pas op. De functie $ n ^ m $ isn ' t polynoom in $ n $ tenzij $ m $ een constante is. En als $ m $ is een constante, het ' heeft geen zin om te zeggen dat de functie exponentieel is in die constante.
- Ja, jij ' hebben gelijk. Ik ' zal dat verduidelijken.
Antwoord
Vaak krijg je een exponentieel brute-force-algoritme voor de tijd als je een probleem overweegt, en de hele zoekruimte opsomt. Typisch zou je aan subsetproblemen denken (in SAT zou je een subset van variabelen ingesteld op true), permutatieproblemen (in TSP is elke tour een permutatie van de steden) en partitieproblemen (in grafiekkleuren probeert u p artitioneer de hoekpunten in kleurklassen). Of overweeg zelfs te sorteren: er zijn $ n! $ Permutaties van $ n $ gehele getallen. Doorloop elke permutatie en controleer of deze is gesorteerd. Gek (en langzaam), maar het werkt.
Reacties
- Merk echter op dat $ O (n!) $ Nog erger is dan $ O ( k ^ n) $. Als je ' nog steeds probeert te leren over tijdcomplexiteit, kan dit nuttig zijn om jezelf te bewijzen.