Quickselect: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
m Bot: parametri del template:Algoritmo in italiano |
m Bot: niente spazi dopo l'apostrofo |
||
Riga 12:
|ottimale = Sì
}}
In [[informatica]], '''quickselect''' è un [[algoritmo]] randomizzato ricorsivo che trova il k-esimo elemento di un [[array]] disordinato di grandezza ''n'' eseguendo [[O-grande|O]](n<sup>2</sup>) confronti nel caso peggiore e [[O-grande|O]](n) nel caso atteso. Si basa sull'
L'algoritmo quicksort ha diverse [[relazione di ricorrenza|relazioni di ricorrenza]], dovute al tipo di problema di minore entità che si viene a creare ogni volta che l'algoritmo viene eseguito. Se ogni chiamata ricorsiva dimezza il problema, si ha:
| |||