Risposta
Un algoritmo è polinomiale (ha tempo di esecuzione polinomiale) se per alcuni $ k, C > 0 $, il suo tempo di esecuzione su input di dimensione $ n $ è al massimo $ Cn ^ k $. In modo equivalente, un algoritmo è polinomiale se per qualche $ k > 0 $, il suo tempo di esecuzione su input di dimensione $ n $ è $ O (n ^ k) $. Questo include lineare, quadratico, cubico e altro. Daltra parte, gli algoritmi con tempi di esecuzione esponenziali non sono polinomiali.
Ci sono cose intermedie: ad esempio, lalgoritmo più noto per il factoring viene eseguito nel tempo $ O (\ exp (Cn ^ {1 / 3} \ log ^ {2/3} n)) $ per qualche costante $ C > 0 $; tale tempo di esecuzione è noto come sottoesponenziale . Altri algoritmi potrebbero essere eseguiti nel tempo $ O (\ exp (A \ log ^ C n)) $ per alcuni $ A > 0 $ e $ C > 1 $, e questi sono noti come quasi-polinomio . Un tale algoritmo è stato recentemente rivendicato per log discreti su caratteristiche piccole.
Commenti
- Vedi anche qui .
- Che cosa sono k e C?
- Sono parametri.
- Quindi gli algoritmi a tempo costante sono considerati polinomiali, corretto?
- Gli algoritmi a tempo costante sono un caso speciale di algoritmi a tempo polinomiale.
Risposta
Lesecuzione di un algoritmo può richiedere del tempo di elaborazione. Dipende principalmente dalla complessità dellalgoritmo. Gli informatici hanno trovato un modo per classificare lalgoritmo in base al suo comportamento di quante operazioni deve eseguire (più operazioni richiedono più tempo).
Una di quella classe mostra la complessità temporale polinomiale. Cioè, la complessità operativa è proporzionale a $ n ^ c $ mentre n è la dimensione dellinput ec è una costante. Ovviamente il nome deriva da $ n ^ c $ che è un polinomio .
Esistono altri “tipi” di algoritmi che richiedono tempo costante indipendentemente dalla dimensione dellinput. Alcuni impiegano $ 2 ^ n $ tempo (sì, davvero slllooooww la maggior parte del tempo).
Lho appena semplificato per i profani e potrei aver introdotto errori. Quindi leggi di più https://stackoverflow.com/questions/4317414/polynomial-time-and-exponential-time
Commenti
- Ho letto su Wolfram che algoritmi di tempo polinomiale sono " veloci " . Tuttavia, ho sentito molte persone dire di preferire algoritmi di tempo logaritmico o lineare rispetto ad algoritmi di tempo polinomiale. Sto fraintendendo luso della parola " veloce "?
- Anche logaritmico e lineare sono polinomiali. Penso che ' veloce ' probabilmente significhi qualcosa come ' molto più pratico per uso reale '.
Risposta
In parole povere il tempo di esecuzione del tuo algoritmo.
Lordine degli algoritmi (crescita) può essere in Big-oh (O), little-oh (o), omega (Ω) o theta (Θ).
Se hai problemi a calcolare il RR, guarda alcune domande che ho fatto prima e vota se hai capito.
Supponi di avere un ciclo for:
for(i=1 to n) x++ Lordine o la complessità temporale di questo pezzo di codice è: O (n)
Perché big-oh? Perché vogliamo il caso peggiore in cui viene eseguito questo pezzo di codice.
Leggi qui (definiscono la complessità di un algoritmo e ti informano su come gli algoritmi vengono eseguiti in tempo polinomiale):
http://en.wikipedia.org/wiki/NP_(complexity) http://en.wikipedia.org/wiki/NP-complete http://en.wikipedia.org/wiki/NP-hard Riepilogo:
http://www.multiwingspan.co.uk/a23.php?page=types
Commenti
- Questo ' non risponde esattamente alla domanda: tempo polinomiale non è " il tempo di esecuzione del tuo algoritmo ". Invece, il tempo di esecuzione di un algoritmo può essere polinomiale e così via. Potresti migliorare la risposta rendendola più precisa. Ad esempio, abbiamo davvero bisogno di leggere 3 articoli di Wikipedia su qualcosa o abbiamo davvero bisogno di sapere qualcosa su Big Oh?