Quickselect: differenze tra le versioni

Contenuto cancellato Contenuto aggiunto
Fabrymondo (discussione | contributi)
Fabrymondo (discussione | contributi)
Migliorata!
Riga 3:
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:
 
<math> T(n) = \mathcal{O}(n) + T({n \over 2})</math>
 
che ha soluzione [[O-grande|O]](n) in base al [[teorema master]].
 
Se invece si è nel caso peggiore, si ottiene: <math> T(n) = \mathcal{O}(n) + T(n - 1)</math> che ha soluzione [[O-grande|O]](n<sup>2</sup>) in base al [[teorema master]].
 
==Implementazione in [[pseudocodice]]==