Confrontiamo la complessità in tempo degli algoritmi di ordinamento ingenui con quella degli algoritmi evoluti, al variare della dimensione del problema
| n | T(n) = n2 (ingenuo) | T(n) = n log2n (evoluto) | ||
|---|---|---|---|---|
| 103 | ~210 | 106 | ~10*103 | ~104 |
| 106 | ~220 | 1012 | ~20*106 | ~107 |
| 109 | ~230 | 1018 | ~30*109 | ~1010 |
| 1012 | ~240 | 1024 | ~40*1012 | ~1013 |
Se un calcolatore svolge 106 operazioni elementari al secondo allora i tempi di attesa sono
| n | n2 | n log2n |
|---|---|---|
| 103 | ~1 secondi | ~0.01 secondi |
| 106 | ~11,5 giorni | ~20 secondi |
| 109 | ~30 mila anni | ~8 ore |
| 1010 | ~3 milioni di anni | ~4 giorni |
Se un calcolatore svolge 109 operazioni elementari al secondo allora i tempi di attesa sono
| n | n2 | n log2n |
|---|---|---|
| 103 | ~0.001 secondi | ~0.00001 secondi |
| 106 | ~17 minuti | ~0.02 secondi |
| 109 | ~30 anni | ~30 secondi |
| 1010 | ~3000 anni | ~5,5 minuti |
Utilizzare un algoritmo ingenuo con milioni di dati porta a tempi di attesa inaccettabili!!!