Quicksort: differenze tra le versioni

Versione delle 01:34, 13 mar 2025

Versione delle 17:14, 31 mar 2025

Riga 138:

Per lo studio nel caso medio si valuta il numero medio di confronti tra elementi del vettore di ingresso eseguiti dall'algoritmo, determinando di conseguenza l'ordine di grandezza del tempo medio di calcolo necessario per eseguire la procedura.

La complessità dell'algoritmo in questo caso è <math>O (n \log_2 (n))</math>, precisamente <math display="inline">1.39\ n \log_2(n)</math>.

=== Caso migliore ===

Il caso migliore si verifica quando l'algoritmo di partizionamento determina due sottoproblemi perfettamente bilanciati, entrambi di dimensione ''n/2''; in questo caso il tempo di esecuzione è <math display="inline">O(n \log_2(n))</math>, precisamente <math display="inline">1.39\ n \log_2(n)</math>.

== Tipi di partizionamento ==