Quickselect: differenze tra le versioni

Versione delle 05:42, 30 ott 2013

Versione delle 12:01, 20 mar 2014

Riga 1:

[[Immagine:Partition example.svg||thumb|right|180pxupright=0.8|Esempio di partizionamento]]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²) confronti nel caso peggiore e [[O-grande|O]](n) nel caso atteso. Si basa sull' algoritmo [[Quicksort]].

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: