Algoritmo di ordinamento: differenze tra le versioni

Versione delle 20:50, 1 dic 2017

Versione delle 19:56, 25 ago 2018

Riga 38:

La ricerca e l'ottimizzazione di algoritmi di ordinamento è molto importante per alcuni ambiti [[Informatica|informatici]] e per queste classi di algoritmi sono stati dimostrati svariati teoremi che ne definiscono i limiti. Il più importante è il seguente:

:''Teorema:'' La [[complessità temporale]] di un qualsiasi algoritmo di ordinamento per confronto è pari a ''Ω<math>\Omega(NlogN)''</math>, dove ''N'' è il numero di elementi da ordinare.

Questo teorema fissa il limite inferiore di complessità per gli algoritmi che si basano sul paragone di coppie di chiavi (per confronto). Nulla è noto su altri algoritmi di ordinamento, nemmeno quali possano essere. Sono stati ipotizzati (ma non prodotti) algoritmi di ordinamento totalmente [[Meccanica quantistica|quantistico]], che potrebbero avere un più basso limite inferiore di complessità.