next up previous
Next: Exercício 2 Up: Exercício 1 Previous: Quicksort Paralelo - Algoritmo

Quicksort Paralelo - Análise

Supondo que o pivot escolhido é sempre a mediana, o algoritmo fará n comparações na primeira partição. No segundo nível de recursividade serão feitas duas partições, cada uma de tamanho n/2; no total serão também feitas n comparações. Entretanto, como as partições são feitas simultaneamente, o tempo gasto será proporcional a n/2. No terceiro nível, teremos quatro partições simultâneas, cada uma de tamanho n/4, e assim por diante. Desta forma, o tempo total gasto será dado pela soma
displaymath3884
Temos portanto um sort com complexidade (para o melhor caso) de tex2html_wrap_inline3896, melhor do que o limite de tex2html_wrap_inline3898 para algoritmos sequenciais.



Osvaldo Sergio F. de Carvalho
Wed Mar 19 14:56:39 EST 1997