|
Numero di operazioni al variare della dimensione del problema
| n | n2
(ingenuo) | nlog2n
(evoluto) |
|---|
| 103 | 106 | ~104 |
|---|
| 106 | 1012 | ~2*107 |
|---|
| 109 | 1018 | ~3*1010 |
|---|
| 1010 | 1020 | ~3,3*1011 |
|---|
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 oggi sul mercato 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 fra qualche anno svolgerà 109 operazioni
elementari al secondo, allora i tempi di attesa saranno
| n | n2 | nlog2n |
|---|
| 103 | ~0.001 sec | |
|---|
| 106 | ~17 min | ~0.02 sec |
|---|
| 109 | ~30 anni | ~30 sec |
|---|
| 1010 | ~3000 anni | ~5,5 min |
|---|
|
