Quote:
|
Originariamente inviato da yorkeiser
Le cartelle della tombola hanno nove righe?? Confesso di non giocare a tombola da molto tempo, ma le ricordo a tre righe  |
Infatti è stato un
lapsus calami. Ho corretto.
Quote:
|
buona l'idea della lista ma forse un pelino pesante; potresti considerare l'opzione di un array bidimensionale, primo campo uguale al numero 1 - 90, secondo campo lo inizializzi con un numero casuale, e fai un ordinamento dell'array sul campo casuale.
|
Affascinante; solo che a quel punto il passo più complesso diventa proprio generare la sequenza pseudorandom
dei valori del secondo campo. Dato che l'algoritmo di ordinamento potrebbe essere stabile, il requisito che i valori pseudorandom siano tutti diversi va lasciato.
Vediamo che succede con una tombola con n numeri.
Se uso la lista, faccio la chiamata pseudorandom in tempo O(1) e ciascuna delle O(n) selezioni in tempo O(n): tempo totale O(n^2).
Se uso l'array, la generazione pseudorandom mi richiede di ricontrollare ogni volta tutta la sequenza delle generazioni precedenti, e questo mi costa comunque tempo O(n^2) per n valori; poi faccio l'ordinamento in tempo
medio O(n log n), e ciascuna delle O(n) selezioni in tempo costante. Il tempo totale mi pare in ogni caso O(n^2).