Quickselect
Da Wikipedia, l'enciclopedia encyclopedia
In informatica, quickselect è un algoritmo randomizzato ricorsivo che trova il k-esimo elemento di un array disordinato di grandezza n eseguendo O(n2) confronti nel caso peggiore e O(n) nel caso atteso. Si basa sull'algoritmo Quicksort e sfrutta la metodologia prune and search.
Questa voce o sezione sull'argomento algoritmi non cita le fonti necessarie o quelle presenti sono insufficienti.
Fatti in breve Classe, Struttura dati ...
Quickselect | |
---|---|
Esempio di partizionamento | |
Classe | Algoritmo di selezione |
Struttura dati | Array |
Caso peggiore temporalmente | |
Caso ottimo temporalmente | |
Caso medio temporalmente | |
Ottimale | Sì |
Chiudi
L'algoritmo quicksort ha diverse 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:
che ha soluzione O(n) in base al teorema master.
Se invece si è nel caso peggiore, si ottiene: che ha soluzione O(n2) in base al teorema master.