Smoothsort: differenze tra le versioni

Versione delle 00:44, 5 mag 2010

Versione delle 11:14, 17 mag 2010

Riga 13:

In [[informatica]] lo '''Smoothsort'''<ref>http://www.cs.utexas.edu/users/EWD/ewd07xx/EWD796a.PDF</ref><ref>http://www.cs.utexas.edu/~EWD/transcriptions/EWD07xx/EWD796a.html</ref> (metodo) è un [[algoritmo di ordinamento]] particolarmente indicato per ordinare liste di dati già parzialmente ordinate. Lo Smoothsort è una variante dell'[[Heap sort]] sviluppata da [[Edsger Dijkstra]] nel [[1981]]: come l'Heap sort anche lo Smoothsort presenta il limite computazionale massimo pari a [[O-grande|O]](''n'' log&nbsp;''n''). Lo Smoothsort, però, si avvicina ad un tempo O(''n'') se [[algoritmi di ordinamento adattivi|i dati in ingresso sono già parzialmente ordinati]], mentre l'Heap sort mediamente impiega O(''n'' log&nbsp;''n''), indifferentemente dal livello di ordinamento iniziale.

==PanoramicaAnalisi==

La lista da ordinare viene divisa in una stringa di [[heap]], ognuna delle quali di dimensione pari ad uno dei [[numero di Leonardo|numeri di Leonardo]] L(n). Il processo di divisione è semplice: i nodi più a sinistra della lista sono divisi nell'heap più grande possibile, ed i rimanenti sono divisi allo stesso modo. Si può dimostrare che:

Riga 229:

</source>

-->

==Riferimenti==

<references/>