Home • ECDL • Algoritmi • Java • Basi di dati • Seconda prova • Eccetera • Cerca nel sito

Ingenui vs. Evoluti

Precedente
SUPERIORE
Successiva

Numero di operazioni al variare della dimensione del problema

nn2
(ingenuo)
nlog2n
(evoluto)
103106~104
1061012~2*107
1091018~3*1010
10101020~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

nn2nlog2n
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

nn2nlog2n
103~0.001 sec
106~17 min~0.02 sec
109~30 anni~30 sec
1010~3000 anni~5,5 min

Ingenui vs. Evoluti - ApPuNtIdIuNiNfOrMaTiCo

Home • ECDL • Algoritmi • Java • Basi di dati • Seconda prova • Eccetera • Cerca nel sito

Precedente
SUPERIORE
Successiva