Svar
En algoritme er polynom (har polynomisk kjøretid) hvis for noen $ k, C > 0 $, er kjøretiden på innganger i størrelse $ n $ maksimalt $ Cn ^ k $. Tilsvarende er en algoritme polynom hvis for noen $ k > 0 $, er kjøretiden på innganger med størrelse $ n $ $ O (n ^ k) $. Dette inkluderer lineær, kvadratisk, kubikk og mer. På den annen side er algoritmer med eksponensielle kjøretider ikke polynom.
Det er ting i mellom – for eksempel kjører den mest kjente algoritmen for factoring i tid $ O (\ exp (Cn ^ {1 / 3} \ log ^ {2/3} n)) $ for noen konstante $ C > 0 $; en slik kjøretid er kjent som undereksponentiell . Andre algoritmer kan kjøre i tid $ O (\ exp (A \ log ^ C n)) $ for noen $ A > 0 $ og $ C > 1 $, og disse er kjent som kvasi-polynom . En slik algoritme har nylig blitt gjort krav på for diskret logg over små egenskaper.
Kommentarer
- Se også her .
- Hva er k og C?
- De er parametere.
- Så konstanttidsalgoritmer blir betraktet som polynomier, riktig?
- Konstanttidsalgoritmer er et spesielt tilfelle av polynomaltidsalgoritmer.
Svar
Å kjøre en algoritme kan ta litt beregningstid. Det avhenger hovedsakelig av hvor kompleks algoritmen er. Dataforskere har gjort en måte å klassifisere algoritmen på grunnlag av dens oppførsel av hvor mange operasjoner den trenger å utføre (flere ops tar mer tid).
En av klassen viser polynomisk tidskompleksitet. Dvs. operasjonell kompleksitet er proporsjonal med $ n ^ c $ mens n er størrelsen på inngangen og c er noe konstant. Åpenbart kommer navnet på grunn av $ n ^ c $ som er et polynom .
Det finnes andre «typer» algoritmer som tar konstant tid uavhengig av størrelsen på inngangen. Noen tar $ 2 ^ n $ tid (ja, virkelig slllooooww det meste av tiden).
Jeg forenklet det for lekmann og kunne ha innført feil. Så les mer https://stackoverflow.com/questions/4317414/polynomial-time-and-exponential-time
Kommentarer
- Jeg leste på Wolfram at polynomialtidsalgoritmer sies å være " raske " . Men jeg hører mange si at de foretrekker logaritmiske eller lineære tidsalgoritmer fremfor polynomiske tidsalgoritmer. Misforstår jeg bruken av ordet " raskt "?
- Logaritmisk og lineær er også polynomisk. Jeg tror ' rask ' sannsynligvis betyr noe sånt som ' mye mer sannsynlig å være praktisk for reell bruk '.
Svar
I lekmannstilstand er det kjøretiden til algoritmen din.
Rekkefølgen av algoritmer (vekst) kan være i Big-oh (O), little-oh (o), omega (Ω) eller theta (Θ).
Hvis du har problemer med å beregne RR, kan du se noen spørsmål jeg spurte før og stemme hvis du forstår.
Si at du har en for loop:
for(i=1 to n) x++ Rekkefølgen eller tidskompleksiteten til dette kodestykket er: O (n)
Hvorfor big-oh? Fordi vi ønsker det verste tilfellet som denne koden kjører.
Les her (disse definerer kompleksiteten til en algoritme og informerer deg om hvordan algoritmer gjøres i polynomisk tid):
http://en.wikipedia.org/wiki/NP_(complexity) http://en.wikipedia.org/wiki/NP-complete http://en.wikipedia.org/wiki/NP-hard Sammendrag:
http://www.multiwingspan.co.uk/a23.php?page=types
Kommentarer
- Dette svarer ikke ' t nøyaktig på spørsmålet: polynomisk tid er ikke " kjøretiden til algoritmen din ". I stedet kan kjøretiden til en algoritme være polynom, og så videre. Du kan gjøre svaret bedre ved å gjøre det mer presist. Må vi for eksempel virkelig lese gjennom 3 Wikipedia-artikler om noe, eller trenger vi til og med å vite noe om Big Oh?