Quickselect: differenze tra le versioni

Versione delle 13:48, 24 mag 2008

Versione delle 23:05, 18 apr 2011

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\left({n \over 2}\right)</math>

che ha soluzione [[O-grande|O]](n) in base al [[teorema master]].