Antwoord
Een algoritme is polynoom (heeft polynoom looptijd) als voor some $ k, C > 0 $, de looptijd op invoer van grootte $ n $ is maximaal $ Cn ^ k $. Op equivalente wijze is een algoritme een polynoom als voor ongeveer $ k > 0 $, de looptijd op invoer van grootte $ n $ $ O (n ^ k) $ is. Dit omvat lineair, kwadratisch, kubisch en meer. Aan de andere kant zijn algoritmen met exponentiële looptijden geen polynoom.
Er zijn dingen tussenin – het bekendste algoritme voor factoring loopt bijvoorbeeld in de tijd $ O (\ exp (Cn ^ {1 / 3} \ log ^ {2/3} n)) $ voor een constante $ C > 0 $; een dergelijke looptijd staat bekend als sub-exponentieel . Andere algoritmen kunnen in tijd $ O (\ exp (A \ log ^ C n)) $ worden uitgevoerd voor ongeveer $ A > 0 $ en $ C > 1 $, en deze staan bekend als quasi-polynoom . Een dergelijk algoritme is zeer recent geclaimd voor discrete logboeking over kleine kenmerken.
Opmerkingen
- Zie ook hier .
- Wat zijn k en C?
- Het zijn parameters.
- Dus constante-tijdalgoritmen worden als polynoom beschouwd, correct?
- Constante-tijdalgoritmen zijn een speciaal geval van polynoom-tijdalgoritmen.
Antwoord
Het uitvoeren van een algoritme kan enige rekentijd in beslag nemen. Het hangt vooral af van hoe complex het algoritme is. Computerwetenschappers hebben een manier gevonden om het algoritme te classificeren op basis van het gedrag van het aantal bewerkingen dat het moet uitvoeren (meer ops nemen meer tijd in beslag).
Een van die klassen vertoont veeltermtijdcomplexiteit. Dat wil zeggen, operationele complexiteit is evenredig met $ n ^ c $, terwijl n de grootte van de invoer is en c een constante. De naam is duidelijk afkomstig van $ n ^ c $, wat een polynoom is.
Er zijn andere “soorten” algoritmen die een constante tijd in beslag nemen, ongeacht de grootte van de invoer. Sommige nemen $ 2 ^ n $ tijd in beslag (ja, echt slllooooww meestal).
Ik heb het net te vereenvoudigd voor de leek en heb misschien fouten geïntroduceerd. Dus lees meer https://stackoverflow.com/questions/4317414/polynomial-time-and-exponential-time
Reacties
- Ik las op Wolfram dat polynomiale tijdalgoritmen " snel " . Ik hoor echter veel mensen zeggen dat ze de voorkeur geven aan logaritmische of lineaire tijdalgoritmen boven polynomiale tijdalgoritmen. Begrijp ik het gebruik van het woord " fast " verkeerd?
- Logaritmisch en lineair zijn ook polynomen. Ik denk dat ' snel ' waarschijnlijk iets betekent als ' veel waarschijnlijker praktisch is voor echt gebruik '.
Antwoord
In lekentaal de looptijd van uw algoritme.
De volgorde van de algoritmen (groei) kan zijn in Big-oh (O), little-oh (o), omega (Ω) of theta (Θ).
Als je problemen hebt met het berekenen van RR, bekijk dan enkele vragen die ik eerder heb gesteld en stem als je het begrijpt.
Stel dat je een for-lus hebt:
for(i=1 to n) x++ De volgorde of tijdcomplexiteit van dit stuk code is: O (n)
Waarom big-oh? Omdat we het slechtste geval willen waarin dit stuk code wordt uitgevoerd.
Lees hier (deze definiëren de complexiteit van een algoritme en informeren u over hoe algoritmen worden uitgevoerd in polynomiale tijd):
http://en.wikipedia.org/wiki/NP_(complexity) http://en.wikipedia.org/wiki/NP-complete http://en.wikipedia.org/wiki/NP-hard Samenvatting:
http://www.multiwingspan.co.uk/a23.php?page=types
Reacties
- Dit geeft ' geen exact antwoord op de vraag: polynomiale tijd is niet " de looptijd van uw algoritme ". In plaats daarvan kan de looptijd van een algoritme polynoom zijn, enzovoort. U kunt het antwoord verbeteren door het nauwkeuriger te maken. Moeten we bijvoorbeeld echt 3 Wikipedia-artikelen over iets lezen, of moeten we eigenlijk zelfs iets weten over Big Oh?