Complessità: ordinamenti

Confrontiamo la complessità in tempo degli algoritmi di ordinamento ingenui con quella degli algoritmi evoluti, al variare della dimensione del problema

n n2
(ingenuo)
nlog2n
(evoluto)
103 106 ~10*10= 104
106 1012 ~20*10= 107
109 1018 ~30*10= 1010
1012 1024 ~40*1012 = 1013

Moltiplicando per 103 il numero di elementi nel vettore, si moltiplica per 106 il numero di operazioni dell’algoritmo ingenuo.

Se un calcolatore svolge 106 operazioni elementari al secondo allora i tempi di attesa sono

n n2 nlog2n
103 ~1 sec ~0.01 sec
106 ~11,5 giorni ~20 sec
109 ~30 mila anni ~8 ore
1010 ~3 milioni di anni ~4 giorni

Se un calcolatore svolgerà, fra qualche anno, 109 operazioni elementari al secondo allora i tempi di attesa saranno

n n2 nlog2n
103 ~0.001 sec ~0.00001 sec
106 ~17 min ~0.02 sec
109 ~30 anni ~30 sec
1010 ~3000 anni ~5,5 min