MO417 - Questão para a prova oral

Numero:

Seja o algoritmo a seguir uma implementação do Randomized-QuickSort, cujo pivô inicial de cada subproblema é definido aleatóriamente entre os elementos A[p, ..., r]

RANDOMIZED-PARTITION(A,p,  r)
1 i <- RANDOM(p, r)
2 trocarA[p] <-> A[i]
3 return PARTITION(A, p, r)


RANDOMIZED-QUICKSORT(A, p, r)
1 if p<r
2  then  q <- RANDOMIZED-PARTITION(A, p, r)
3          RANDOMIZED-QUICKSORT(A, p, q - 1)
4          RANDOMIZED-QUICKSORT(A, q + 1, r) 

Podemos afirmar que:

a.   Para a entra {2,1,1,1,1,1}, tanto Randomized-QuickSort e QuickSort obterão o mesmo número e tamanho dos subproblemas.
b.  O custo de dividir e conquistar no Randomized-QuickSort é menor que o custo para o QuickSort, supondo que a geração de número aleatório seja constante para qualquer entrada.
c.  O algoritmo Randomized-QuickSort amortiza o custo do pior caso do QuickSort, assim seu custo em ordem temporal é sempre menor ou igual ao custo do QuickSort para qualquer caso.
d.  Sabendo que a entrada contém elementos distintos em alguma ordenação, o Randomized-QuickSort terá menores chances de gerar subproblemas K e L, onde K é muito maior que L, em comparação ao QuickSort.
e. N.D.A

Ideia original de: Otávio Augusto Araújo Silva