Quote:
Originariamente inviato da yorkeiser
una visione un attimino ingegneristica del problema sarebbe quella di generare dei numeri casuali elevati (supponiamo da 0 a 100000), così puoi tranquillamente evitare il controllo a ritroso sull'uguaglianza: su un tetto di 100.000, senza tirar fuori manuali di calcolo combinatorio, la probabilità che tiri fuori 2 numeri uguali, anche su 90 estrazioni, è MOLTO bassa; anche se succedesse, non inficierebbe di certo il funzionamento del programma.
|
L'errore sta proprio nel punto finale: a robs05 non serve un programma che "fallisce con probabilità bassa", ma glie ne serve uno che riesca sempre.
Quote:
Resta la complessità relativa all'ordinamento, che non è logaritmica ma dal mio punto di vista addirittura quadratica visto che un semplice bubble sort, per soli 90 numeri e su un processore a X Ghz, magari riuscirà ad avere un tempo di esecuzione minore di infinito.
|
Un algoritmo corretto, eseguito su un input di grandezza finita, ha
sempre tempo di esecuzione finito.
E poi, per 90 numeri su un P4 turbo intercooler non è il caso di preoccuparsi
troppo.