Svar
En algoritme er polynom (har polynom kørselstid), hvis nogle $ k, C > 0 $, dens driftstid på input af størrelse $ n $ er højst $ Cn ^ k $. Tilsvarende er en algoritme polynom, hvis den for nogle $ k > 0 $, dens driftstid på input af størrelse $ n $ er $ O (n ^ k) $. Dette inkluderer lineær, kvadratisk, kubisk og mere. På den anden side er algoritmer med eksponentielle køretider ikke polynomier.
Der er ting imellem – for eksempel kører den bedst kendte algoritme til factoring i tiden $ O (\ exp (Cn ^ {1 / 3} \ log ^ {2/3} n)) $ for noget konstant $ C > 0 $; sådan en køretid er kendt som undereksponentiel . Andre algoritmer kunne køre i tid $ O (\ exp (A \ log ^ C n)) $ for nogle $ A > 0 $ og $ C > 1 $, og disse er kendt som kvasi-polynom . En sådan algoritme er for nylig blevet hævdet for diskret log over små karakteristika.
Kommentarer
- Se også her .
- Hvad er k og C?
- De er parametre.
- Så konstant tidsalgoritmer betragtes som polynomiske, korrekte?
- Konstant tidsalgoritmer er et specielt tilfælde af polynomiske tidsalgoritmer.
Svar
At køre en algoritme kan tage noget beregningstid. Det afhænger primært af, hvor kompleks algoritmen er. Computerforskere har gjort en måde at klassificere algoritmen på baggrund af dens opførsel af, hvor mange operationer den har brug for at udføre (flere ops tager mere tid).
En af denne klasse viser polynomisk tidskompleksitet. Dvs. operationel kompleksitet er proportional med $ n ^ c $, mens n er størrelsen på input og c er noget konstant. Navnet kommer naturligvis på grund af $ n ^ c $, som er et polynom .
Der er andre “typer” algoritmer, der tager konstant tid uanset inputstørrelsen. Nogle tager $ 2 ^ n $ tid (ja, virkelig slllooooww det meste af tiden).
Jeg forenklede det for lidt for lægmanden og har muligvis introduceret fejl. Så læs mere https://stackoverflow.com/questions/4317414/polynomial-time-and-exponential-time
Kommentarer
- Jeg læste på Wolfram, at polynomaltidsalgoritmer siges at være " hurtige " . Men jeg hører mange mennesker sige, at de foretrækker logaritmiske eller lineære tidsalgoritmer frem for polynomiske tidsalgoritmer. Misforstår jeg brugen af ordet " hurtigt "?
- Logaritmisk og lineær er også polynomisk. Jeg tror ' hurtig ' sandsynligvis betyder noget som ' meget mere sandsynligt at være praktisk for reel brug '.
Svar
I lægmandssæt kørselstiden for din algoritme.
Rækkefølgen af algoritmer (vækst) kan være i Big-oh (O), little-oh (o), omega (Ω) eller theta (Θ).
Hvis du har problemer med at beregne RR, bedes du se nogle af de spørgsmål, jeg har stillet før, og stemme, hvis du forstår.
Sig, at du har en for loop:
for(i=1 to n) x++ Rækkefølgen eller tidskompleksiteten af dette stykke kode er: O (n)
Hvorfor stor-åh? Fordi vi ønsker det værste tilfælde, hvor dette stykke kode kører.
Læs her (disse definerer kompleksiteten af en algoritme og informerer dig om, hvordan algoritmer udfø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 Resume:
http://www.multiwingspan.co.uk/a23.php?page=types
Kommentarer
- Dette svarer ikke ' t nøjagtigt til at svare på spørgsmålet: polynomisk tid er ikke " kørselstiden for din algoritme ". I stedet for kan en algoritmes driftstid være polynomisk og så videre. Du kan gøre svaret bedre ved at gøre det mere præcist. Har vi for eksempel virkelig brug for at læse igennem 3 Wikipedia-artikler om noget, eller har vi faktisk engang brug for at vide noget om Big Oh?