Algoritmo: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
m Annullate le modifiche di 176.201.18.180 (discussione), riportata alla versione precedente di Nubifer Etichette: Rollback Annulla |
→Studio della complessità computazionale di un algoritmo: tolgo link errato |
||
Riga 121:
Ad esempio, in un algoritmo di [[ricerca lineare]], se l'elemento cercato è il primo della lista ci troviamo nel caso migliore, <math>T_{migliore}(n)=1</math>. La complessità nel caso medio è <math>T_{medio}(n)=\frac{1}{n} \sum_{i=1}^n i = (n+1)/2</math>. Nel caso peggiore l'elemento cercato è l'ultimo della lista: in questo caso <math>T_{peggiore}(n)=n</math>, ossia sono richiesti tutti gli <math>n</math> passi per trovare la soluzione.
Il caso peggiore è quello che viene solitamente considerato per descrivere la complessità di un algoritmo. In alcuni casi (ad esempio il [[quicksort]]) viene considerato il caso medio, poiché il caso peggiore avviene molto raramente o addirittura con
=== Complessità e stabilità ===
| |||