Analisi della complessità del quicksort
ciao a tutti 
Sto studiando l'algoritmo di ordinamento quicksort e non capisco come mai nel caso medio esso si comporti come nel caso ottimo cioè quando le partizioni sono sempre bilanciate.
Qualcuno può spiegarmelo in modo semplice per favore? Ho cercato su internet ma danno molte cose per scontato. Non voglio imparare la formula a memoria ma voglio capirla.
Grazie in anticipo
Sto studiando l'algoritmo di ordinamento quicksort e non capisco come mai nel caso medio esso si comporti come nel caso ottimo cioè quando le partizioni sono sempre bilanciate.
Qualcuno può spiegarmelo in modo semplice per favore? Ho cercato su internet ma danno molte cose per scontato. Non voglio imparare la formula a memoria ma voglio capirla.
Grazie in anticipo
Risposte
Ciao,
Il caso medio di quicksort e' relativamente difficile da dimostrare. In pratica si usa la randomizzazione, cioe' scegliere ad ogni passo un nuovo pivot. Si puo' dimostrare che facendo cosi hai bisogno solo di una certa percentuale di pivot "ottimi" (cioe' che divide l'array in 2 parti), mi sembra sia ~30-40%. Quindi da tutti i pivot che scegli ogni volta che dividi l'array solo 40% di questi devono dividere l'array in piu' o meno due parti uguali.
Il caso medio di quicksort e' relativamente difficile da dimostrare. In pratica si usa la randomizzazione, cioe' scegliere ad ogni passo un nuovo pivot. Si puo' dimostrare che facendo cosi hai bisogno solo di una certa percentuale di pivot "ottimi" (cioe' che divide l'array in 2 parti), mi sembra sia ~30-40%. Quindi da tutti i pivot che scegli ogni volta che dividi l'array solo 40% di questi devono dividere l'array in piu' o meno due parti uguali.
quindi è solo un caso di probabilità?
Si.
Grazie mille
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo