MO417 - QUESTÃO PARA A PROVA ORAL
Número: 2013-030
Enunciado: Leonardo prestou um concurso público com 30 vagas e está tentando descobrir sua classificação final. Entretanto, foi divulgada apenas uma lista na qual cada elemento possui o número de inscrição de um candidato e sua respectiva nota final. Infelizmente, a lista está ordenada pelo número de inscrição e não pela nota. Para saber se foi aprovado, Leonardo precisa comparar sua nota com a do candidato que ficou em 30o. lugar.
Considerando o estado da arte em teoria de algoritmos, o que podemos oferecer a pessoas que queiram obter o 30o. elemento numa lista de tamanho n?
- Os melhores algoritmos conhecidos para este problema gastam Ω(n lg n) unidades de tempo.
- É possível conseguir a resposta desejada em tempo linear em n.
- Exsitem algoritmos que resolvem tais problemas em tempo O(lg n).
- Nenhum algoritmo para este problema usa menos do que tempo Ω(n²).
- N. D. A.
Nenhum comentário:
Postar um comentário