Quickselect: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
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]]==
|