MO417 - Questão para a prova oral
Número: 029
Enunciado:
Considere o algoritmo SELECT(A, i, n), o qual encontra o i-ésimo menor elemento de um arranjo A contendo n elementos distintos. Tal algoritmo pode ser projetado da seguinte forma:
- Divida os n elementos em ⌊n/5⌋ subconjuntos de 5 elementos e um subconjunto de n mod 5 elementos.
- Encontre a mediana de cada um dos ⌈n/5⌉ subconjuntos usando um método simples de ordenação, como o INSERTION-SORT.
- Determine, recursivamente, a mediana x das medianas dos subconjuntos de 5 elementos.
- Particione o arranjo original A por meio do algoritmo PARTITION, do QUICK-SORT, tomando x como pivô, criando dois arranjos: A<, que contém elementos menores que x, e A>, contendo elementos maiores que x.
- Seja k a posição de x após a execução de PARTITION. Compare os valores de k e de i da seguinte forma:
- Se k = i, retorne o elemento x, que neste caso será A[i].
- Se k < i, determine, recursivamente, o i-ésimo menor elemento do subarranjo A<.
- Se k > i, determine, recursivamente, o (k-i)-ésimo menor elemento do subarranjo A>.
No pior caso, o algoritmo acima é executado em tempo O(n).
Suponha uma modificação dessa
implementação de SELECT, na qual os elementos
são divididos em ⌊n/6⌋ subconjuntos de
6 elementos e um subconjunto de n mod 6 elementos, tomando
então a mediana inferior de cada subconjunto, além do uso do MERGE-SORT no lugar do INSERTION-SORT na segunda etapa. Neste caso, o tempo de execução de SELECT, no pior caso, será de:
- O(n2 lg n)
- O(n2)
- O(n lg n)
- O(n)
- NDA
Autor(a): Marcos Vinícius Mussel Cirne