Complessità degli 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) evoluto / ingenuo
103 106 ~104 10-2
106 1012 ~2*107 2*10-5
109 1018 ~3*1010 3*10-8
1010 1020 ~3,3*1011 3,3*10-9

Moltiplicando per 103 il numero di elementi nel vettore, si moltiplica per 106 il numero di operazioni dell’algoritmo ingenuo (per ~104 il numero di operazioni dell’algoritmo evoluto…).

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
Notice: This work is licensed under a BY-NC-SA. Permalink: Complessità degli ordinamenti

Comments are closed.