Quickselect: differenze tra le versioni

Versione delle 17:39, 15 gen 2015

Versione delle 17:27, 21 giu 2015

Riga 1:

{{F|informatica|agosto 2014}}

{{tmp|Algoritmo}}

|name=Quickselect

[[Immagine:Partition example.svg|thumb|upright=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]] e sfrutta la metodologia [[prune and search]].

|class=Algoritmo di selezione

|image=[[File:Partition example.svg|200px]]

|caption=Esempio di partizionamento

|data=[[Array]]

|best-time= <math>O(n)</math>

|average-time=<math>O(n)</math>

|time=<math>O(n^2)</math>

|space=

|optimal=Sì

}}

[[Immagine:Partition example.svg|thumb|upright=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]] e sfrutta la metodologia [[prune and search]].

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: