Analisi della complessità del quicksort

noipo
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 :D

Risposte
jack012
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.

noipo
quindi è solo un caso di probabilità?

jack012
Si.

noipo
Grazie mille :)

Rispondi
Per rispondere a questa discussione devi prima effettuare il login.