Svar
En algoritm är polynom (har polynom körtid) om för vissa $ k, C > 0 $, dess körtid på ingångar i storlek $ n $ är högst $ Cn ^ k $. På motsvarande sätt är en algoritm polynom om för vissa $ k > 0 $, dess körtid på ingångar i storlek $ n $ är $ O (n ^ k) $. Detta inkluderar linjär, kvadratisk, kubisk och mer. Å andra sidan är algoritmer med exponentiella körtider inte polynomiska.
Det finns saker däremellan – till exempel, den mest kända algoritmen för factoring körs i tiden $ O (\ exp (Cn ^ {1 / 3} \ log ^ {2/3} n)) $ för någon konstant $ C > 0 $; en sådan körtid kallas sub-exponential . Andra algoritmer kan köras i tid $ O (\ exp (A \ log ^ C n)) $ för vissa $ A > 0 $ och $ C > 1 $, och dessa kallas kvasi-polynom . En sådan algoritm har nyligen gjort anspråk på diskret logg över små egenskaper.
Kommentarer
- Se även här .
- Vad är k och C?
- De är parametrar.
- Så konstanta tidsalgoritmer betraktas som polynomier, korrekta?
- Konstanttidsalgoritmer är ett speciellt fall av polynomiska tidsalgoritmer.
Svar
Att köra en algoritm kan ta lite datatid. Det beror främst på hur komplex algoritmen är. Datavetare har gjort ett sätt att klassificera algoritmen baserat på dess beteende för hur många operationer den behöver utföra (fler ops tar mer tid).
En av den klassen visar polynomisk tidskomplexitet. Dvs operationell komplexitet är proportionell mot $ n ^ c $ medan n är storleken på ingången och c är konstant. Självklart kommer namnet på grund av $ n ^ c $ vilket är ett polynom .
Det finns andra ”typer” av algoritmer som tar konstant tid oberoende av ingångens storlek. Vissa tar $ 2 ^ n $ tid (ja, verkligen slllooooww för det mesta).
Jag har förenklat det för lekmannen och kan ha infört fel. Så läs mer https://stackoverflow.com/questions/4317414/polynomial-time-and-exponential-time
Kommentarer
- Jag läste på Wolfram att algoritmer för polynomtid sägs vara " snabb " . Men jag hör att många säger att de föredrar logaritmiska eller linjära tidsalgoritmer framför polynomiska tidsalgoritmer. Missförstår jag användningen av ordet " snabbt "?
- Logaritmisk och linjär är också polynom. Jag tror att ' snabbt ' förmodligen betyder något som ' mycket mer sannolikt att vara praktiskt för verklig användning '.
Svar
I lekmanns termer är det algoritmens körtid.
Algoritmernas ordning (tillväxt) kan vara i Big-oh (O), little-oh (o), omega (Ω) eller theta (Θ).
Om du har problem med att beräkna RR, se några frågor jag ställde tidigare och rösta om du förstår.
Säg att du har en för loop:
for(i=1 to n) x++ Ordningen eller tidskomplexiteten för denna kod är: O (n)
Varför stor-oh? Eftersom vi vill ha det värsta fallet då denna kod körs.
Läs här (dessa definierar komplexiteten hos en algoritm och informerar dig om hur algoritmer görs i polynomtid):
http://en.wikipedia.org/wiki/NP_(complexity) http://en.wikipedia.org/wiki/NP-complete http://en.wikipedia.org/wiki/NP-hard Sammanfattning:
http://www.multiwingspan.co.uk/a23.php?page=types
Kommentarer
- Detta svarar inte ' t exakt på frågan: polynomtid är inte " din algoritms ". Istället kan en algoritmes körtid vara polynomisk och så vidare. Du kan göra svaret bättre genom att göra det mer exakt. Behöver vi till exempel verkligen läsa igenom tre Wikipedia-artiklar om något, eller behöver vi faktiskt ens veta något om Big Oh?