MO417 - QUESTÃO PARA A PROVA ORAL

Número: 

Dado o problema de encontrar o k-ésimo menor elemento de um arranjo A com n elementos, das soluções abaixo qual é a mais rápida assintoticamente?

1. Encontrar e retirar o menor elemento do arranjo A por k vezes
2. Ordenar o arranjo A com MERGE-SORT e retornar o valor A[k]
3. Utilizar o particionamento do QUICKSORT recursivamente para produzir sub-arranjos de A até que o PIVOT seja o elemento A[k]
4. Construir um heap máximo e retirar o elemento raiz  ( n-k ) vezes, aplicando MAX-HEAPFY na raiz em cada retirada
5. NDA

Ideia original de: Daniel Vidal