Insertion sort: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Riga 86:
'''1''' 2 3 4 5 6 7 9
== Analisi delle prestazioni ==
Il caso ottimo per l'algoritmo è quello in cui la sequenza di partenza sia già ordinata. In questo caso, l'algoritmo ha tempo di esecuzione lineare, ossia <math>\Theta(n)</math>. Infatti, in questo caso, in ogni iterazione il primo elemento della sottosequenza non ordinata viene confrontato solo con l'ultimo della sottosequenza ordinata.
Il caso pessimo è invece quello in cui la sequenza di partenza sia ordinata al contrario. In questo caso, ogni iterazione dovrà scorrere e spostare ogni elemento della sottosequenza ordinata prima di poter inserire il primo elemento della sottosequenza non ordinata. Pertanto, in questo caso l'algoritmo di insertion sort ha complessità temporale quadratica, ossia <math>\Theta(n^2)</math>.
| |||