Time Complexity
Da cppreference.com.
< cpp
Ci sono differenti misure della velocità di un algoritmo. Se la dimensione dell'input di un algoritmo è N la velocità di elaborazione viene descritta nei seguenti modi:
| None | Velocità | Descrizione | Formula | Esempio |
|---|---|---|---|---|
| tempo fattoriale | molto lento | impiega un tempo proporzionale a N elevato alla N-esima potenza | N! | Soluzione a "forza bruta" del problema del "commesso viaggiatore" |
| tempo esponenziale | lento | impiega un tempo proporzionale ad una costante elevata all'N-esima potenza | KN | Soluzione a forza bruta del Cubo di Rubik |
| tempo polinomiale | veloce | impiega un tempo proporzionale ad N elevato a qualche potenza costante | NK | Ordinamento per confronto (bubble sort, insertion, selection sort) |
| tempo "linearitmico" | molto veloce | impiega un tempo nella regione tra lineare e polinomiale | N*log(N) | Ordinamenti logaritmici lineari (quicksort, heapsort, mergesort) |
| tempo lineare | superveloce | impiega un tempo proporzionale ad N | K*N | Iterazione attraverso un array |
| tempo logaritmico | velocissimo | impiega un tempo proporzionale al logaritmo di N | K*log(N) | Ricerca binaria |
| tempo costante | ideale | impiega un tempo costante indipendentemente dall'input | K | lookup tramite indice di un elemento in un array |
[modifica]Analisi della complessità
Un'operazione data può avere diverse complessità a seconda dell'ordine e del tipo di input. I diversi metodi di determinazione nell'analisi della complessità temporale sono i seguenti:
| Name | Description | Example |
|---|---|---|
| best-case | Un caso dove l'operazione esegue il più velocemente possibile | Il "bubblesort" ha una complessita di best-case dell'ordine di N |
| average-case | Un caso dove l'operazione esegue in tempo confrontabile con quello della maggiranza dei casi possibili | Il Quicksort ha una complessità di average-case di N * log(N) |
| worst-case | Un caso dove l'operazione esegue nel modo più lento | Il Quicksort ha una complessitù di worst-case di N2 |
| amortized worst-case | La stima della media del worst-case presa su un infinito numero di input | vector::push_back() ha un amortized worst-case di K (constant time) |
Scegliere l'algoritmo giusto dipende da quali casi vi aspettate di incontrare nella vostra applicazione. Per esempio un applicazione che deve proteggersi da input "malicious" dovrà evitare implementazioni "semplici" del quicksort, che ha una complessità di worst-time di N2, nonostante abbia una delle più veloci esecizioni in average-case rispetto agli altri sort.
