Kan iemand het verschil uitleggen tussen algoritmen voor polynomiale tijd, niet-polynomiale tijd en exponentiële tijd?
Als een algoritme bijvoorbeeld O(n^2) tijd kost, in welke categorie valt het dan?
Antwoord 1, autoriteit 100%
Bekijk dituit.
Exponentieel is erger dan polynoom.
O(n^2) valt in de kwadratische categorie, wat een soort polynoom is (het speciale geval van de exponent is gelijk aan 2) en beter dan exponentieel.
Exponentieel is veelerger dan polynoom. Kijk hoe de functies groeien
n = 10 | 100 | 1000
n^2 = 100 | 10000 | 1000000
k^n = k^10 | k^100 | k^1000
k^1000 is uitzonderlijk groot, tenzij k kleiner is dan zoiets als 1.1. Zoiets als elk deeltje in het universum zou 100 miljard miljard miljard bewerkingen per seconde moeten doen gedurende biljoenen miljarden miljarden jaren om dat voor elkaar te krijgen.
Ik heb het niet uitgerekend, maar HET IS ZO GROOT.
Antwoord 2, autoriteit 92%
Hieronder staan enkele veelvoorkomende Big-O-functies bij het analyseren van algoritmen.
- O(1) – constante tijd
- O(log(n)) – logaritmische tijd
- O((log(n))c) – polylogaritmische tijd
- O(n) – lineaire tijd
- O(n2) – kwadratische tijd
- O(nc) – polynomiale tijd
- O(cn) – exponentiële tijd
- O(n!) – faculteitstijd
(n = grootte van invoer, c = een constante)
Hier is de modelgrafiek die de Big-O-complexiteit van sommige functies weergeeft
proost 🙂
grafiektegoeden http://bigocheatsheet.com/
Antwoord 3, autoriteit 49%
O(n^2) is polynomiale tijd. De polynoom is f(n) = n^2. Aan de andere kant is O (2 ^ n) exponentiële tijd, waarbij de impliciete exponentiële functie f (n) = 2 ^ n is. Het verschil is of de functie van n n in de basis van een machtsverheffing plaatst, of in de exponent zelf.
Elke exponentiële groeifunctie zal aanzienlijk sneller groeien (op lange termijn) dan elke polynoomfunctie, dus het onderscheid is relevant voor de efficiëntie van een algoritme, vooral voor grote waarden van n.
Antwoord 4, autoriteit 23%
Polynomiale tijd.
Een polynoom is een som van termen die eruitzien als Constant * x^k
Exponentieel betekent zoiets als Constant * k^x
(in beide gevallen is k een constante en x een variabele).
De uitvoeringstijd van exponentiële algoritmen groeit veel sneller dan die van polynomiale.
Antwoord 5, autoriteit 21%
Exponentieel(Je hebt een exponentiële functie als MINIMAAL EEN EXPONENT afhankelijk is van een parameter):
- Bijvoorbeeld f(x) = constante ^ x
Polynoom(u hebt een polynoomfunctie als GEEN EXPONENT afhankelijk is van sommige functieparameters):
- Bijvoorbeeld f(x) = x ^ constante
Antwoord 6, autoriteit 3%
polynomiale tijd O(n)^k betekent dat het aantal bewerkingen evenredig is met de macht k van de grootte van de invoer
exponentiële tijd O(k)^n betekent Aantal bewerkingen is evenredig met de exponent van de invoergrootte
Antwoord 7
o(n sequre) is polynimale tijdcomplexiteit terwijl o(2^n) exponentiële tijdcomplexiteit is
if p=np in het beste geval, in het slechtste geval p=np niet gelijk omdat wanneer de invoergrootte n zo lang groeit of de invoergrootte zo lang toeneemt, het in het slechtste geval en de afhandeling gaat, zodat de groeisnelheid van de complexiteit toeneemt en afhankelijk is van de invoergrootte wanneer de invoer klein is, is het polynimaal wanneer de invoergrootte groot en groot is, dus p=np is niet gelijk, het betekent dat de groeisnelheid afhankelijk is van de grootte van invoer “N”.
optimalisatie, sat, clique en independ set ontmoetten elkaar ook in exponentieel tot polynimaal.
Antwoord 8
Hier is de eenvoudigste uitleg voor beginners:
Een veelterm:
als een uitdrukking bevat of functie gelijk is aan wanneer een constante de macht van een variabele is, bijvoorbeeld
f(n) = 2 ^ n
terwijl
Een exponentieel:
als een uitdrukking bevat of een functie qual is aan wanneer een variabele de macht van een constante is, bijvoorbeeld
f(n) = n ^ 2
Antwoord 9
Nauwkeurigere definitie van exponentieel
De definitie van polynoomis vrijwel universeel en duidelijk, dus ik zal het niet bespreken verder.
De definitie van Big Ois ook vrij universeel, je moet er alleen goed over nadenken de Men de x0in de Wikipedia-definitie en doorloop enkele voorbeelden.
Dus in dit antwoord wil ik me concentreren op de precieze definitie van exponentieel, omdat het wat meer aandacht vereist/minder bekend is/minder universeel is, vooral als je begint na te denken over enkele randgevallen. Ik zal het dan iets verderop contrasteren met polynomen
- https://cstheory.stackexchange.com/questions /22588/is-it-right-to-call-2-sqrtn-exponential
- https://math.stackexchange.com /questions/55468/hoe-te-bewijzen-dat-exponentiële-groeit-sneller-dan-polynoom
De meest gebruikelijke definitie van exponentiële tijd is:
2^{polymonial(n)}
waarbij polynomialeen polynoom is dat:
- is niet constant, b.v.
1, anders is de tijd ook constant - de term van de hoogste orde heeft een positieve coëfficiënt, b.v.
-2n, anders gaat het naar nul op oneindig
bijv.:
2^{n^2 + 2n + 1}
Merk op dat de basis 2 elk willekeurig getal kan zijn > 1 en de definitie zou nog steeds geldig zijn omdat we de basis kunnen transformeren door de exponent te vermenigvuldigen, bijvoorbeeld:
8^{polymonial(n)} = (2^3)^{polymonial(n)} = 2^{3 * polymonial(n)}
en 3 * polymonial(n)is ook een polynoom.
Houd er ook rekening mee dat toevoeging er niet toe doet, b.v. 2^{n + 1} = 2 * 2^{n}en dus maakt de + 1niet uit voor de grote O-notatie.
Daarom ziet de kleinste exponentiële in de grote O-notatie er als volgt uit:
(1 + e)^{n}
voor zeer kleine e. De hoogste ordeterm is n^1, bestel één.
Superpolynoom en sub-exponentieel
Maar houd er rekening mee dat de bovenstaande definitie enkele nog steeds zeer grote dingen uitsluit die in de praktijk opduiken en dat we in de verleiding zouden komen om “exponentieel” te noemen, bijvoorbeeld:
2^{n^{1/2}}. Dit lijkt een beetje op een polynoom, maar het is geen polynoom omdat polynomiale machten gehele getallen moeten zijn, en hier hebben we1/22^{log_2(n)^2}
Die functies zijn nog steeds erg groot, omdat ze sneller groeien dan welke polynoom dan ook.
Maar strikt genomen zijn ze grote O kleiner dan de polynomen in onze strikte definitie!
Dit motiveert de volgende definities:
- superpolynoom: groeit sneller dan welke polynoom dan ook
- subexponentieel: groeit minder snel dan exponentieel, d.w.z.
(1 + e)^{n}
en alle voorbeelden hierboven in deze sectie vallen in die categorie.
Houd er rekening mee dat als je iets heel kleins op de exponentieel zet, het natuurlijk terug kan gaan naar polynoom, bijvoorbeeld:
2^{log_2(n)} = n
En dat geldt ook voor alles kleiner dan log_2, bijvoorbeeld:
2^{log_2(log_2(n))} = log_2(n)
is sub-polynoom.
Belangrijke superpolynoom- en subexponentiële voorbeelden
-
de algemene nummerveldzeefhet snelst bekende algoritme voor integer-factorisatie, met complexiteit van de vorm
2^{(k + o(1))(log(n)^(1/3) * log(log(n)))^(2/3)}Daar betekent de kleine-o-notatie
o(1)een term die op oneindig naar 0 gaat.Die complexiteit heeft zelfs een benoemde generalisatie zoals die vermoedelijk voorkomt in andere analyses: L-notation.
Het fantastische antwoord op: Waarom zou een algoritme O(log log n) complexiteit hebben?geeft een intuïtieve uitleg van waar de
O(log log n)vandaan komt: terwijllog nkomt van een algoritme dat bij elke stap de helft van de opties verwijdert, enlog log nkomt van een algoritme dat de opties bij elke stap reduceert tot de vierkantswortel van het totaal!
https ://math.stackexchange.com/questions/3975382/what-problems-are-known-to-be-require-superpolynomial-time-or-greater-to-solvevraagt naar interessante algoritmen die zijn bewezen superpolynoom (en vermoedelijk met bewijs van optimaliteit, anders zou de algemene getallenzeef een voor de hand liggende keuze zijn, maar we weten niet of deze optimaal is of niet)
Bewijs dat exponentieel altijd groter is dan polynoom op oneindig
Discussies over verschillende mogelijke definities van sub-exponentieel
- https://cstheory.stackexchange.com/questions /22588/is-it-right-to-call-2-sqrtn-exponential
- https://math.stackexchange.com / Vragen / 55468 / How-to-bewijs – dat-exponentiële groeit-sneller-dan-polynomiale
- https: //en.wikipedia .org / w / index.php? titel = time_complexity & amp; oldid = 1026049783 # sub-exponential_time