Compare dois métodos para obter o maior elemento em um conjunto de n dados: (A) varrer a lista e manter o…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Comparar diferentes casos particulares (instâncias) de um mesmo problema, identificando as semelhanças e diferenças entre eles, e criar um algoritmo para resolver todos, fazendo uso de variáveis (parâmetros) para permitir o tratamento de todos os casos de forma genérica.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Compare dois métodos para obter o maior elemento em um conjunto de n dados: (A) varrer a lista e manter o máximo (um passe); (B) ordenar a lista e então escolher o último elemento. Qual método tem menor complexidade assintótica e por quê?
- A) O método A é mais eficiente: complexidade O(n) versus O(n log n) da ordenação.
- B) Varrer a lista exige O(n^2) por comparar todos os pares.
- C) Ambos têm mesma complexidade O(n).
- D) Ordenação tem complexidade O(log n), logo é superior.
- E) Ordenar e pegar o último é mais eficiente: O(n) contra O(n log n).
✅ Resposta correta: alternativa A
Resolução passo a passo
- Analise o método A. Varrer a lista uma única vez, mantendo o maior valor visto até o momento, exige uma comparação por elemento. Logo, são aproximadamente n comparações, o que dá complexidade O(n).
- Analise o método B. Ordenar uma lista com algoritmos eficientes de comparação (como merge sort ou heap sort) custa O(n log n) no caso médio e no pior caso. Depois de ordenada, escolher o último elemento custa O(1), que não altera a ordem de grandeza. Portanto, o método B custa O(n log n).
- Compare as ordens de crescimento. Como log n cresce com n, n log n cresce mais rápido que n. Assim, para listas grandes, o método A é assintoticamente mais eficiente.
- Verifique as alternativas erradas. A alternativa B está errada porque o método A não compara todos os pares; ele faz uma única passada. A alternativa C está errada porque o método B não é O(n), já que a ordenação custa O(n log n). A alternativa D está errada porque a ordenação não é O(log n): ela precisa de pelo menos n leituras para processar os dados. A alternativa E está errada porque inverte a conclusão: O(n) é melhor que O(n log n), e não o contrário, sendo o método A o mais eficiente.
- Conclusão. O método A (varredura linear) tem menor complexidade assintótica, O(n), contra O(n log n) da ordenação, pois não precisa organizar todos os elementos para descobrir apenas o maior. O gabarito A está correto.
💡 Dica: Analise a complexidade de cada método antes de comparar.
Alternativa por alternativa
Varrer uma vez compara cada item uma vez (O(n)); ordenar envolve custos de comparação/redistribuição que tipicamente são O(n log n), portanto maior para grandes n.
O aluno acredita que encontrar o máximo exige comparar todos os pares de elementos, como em um laço aninhado. Ele confunde a varredura linear com a comparação de cada elemento com todos os outros.
Por que engana: Confundir a complexidade de varrer a lista com a de ordenar, acreditando que ambos os métodos têm a mesma eficiência.
O aluno considera que ordenar e varrer têm o mesmo custo linear, ignorando que a ordenação exige O(n log n). Ele não percebe que o passo de ordenação domina a complexidade do método B.
O aluno confunde a complexidade da ordenação com a da busca binária, atribuindo O(log n) ao processo de ordenar. Ele também ignora que a ordenação precisa tratar todos os n elementos.
O aluno inverte a comparação entre as ordens de crescimento, achando que O(n log n) é menor que O(n). Ele confunde a sentença com a conclusão e escolhe o método de ordenação como o mais eficiente.
Raio-X da questão
complexidade assintótica
avaliacao
complexidade assintótica · análise de algoritmos
Revisar conceitos de complexidade de algoritmos e métodos de ordenação.
Confundir a complexidade de varrer a lista com a de ordenar, acreditando que ambos os métodos têm a mesma eficiência.
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Em um código, você precisa percorrer uma lista para encontrar o maior número. Qual algoritmo utilizar?
- Em um exercício de preparação para períodos de chuva intensa, uma central municipal de Defesa Civil precisa localizar…
- Ao comparar dois algoritmos de ordenação para conjuntos de dados grandes, qual medida assintótica do algoritmo é mais…
- Considere dois algoritmos para processar n registros: A tem complexidade O(n log n) e B tem O(n). Para valores grandes…
- Considere que você tenha que criar um algoritmo para encontrar o maior número em uma lista. Quais são os passos que você…
- Uma escola pública brasileira criou dois algoritmos para verificar se determinado estudante está matriculado. A lista de…
Todas as questões de Estratégias de solução de problemas - Generalização
🔎 Procurar outra questão
Procure no banco do GeraProva pelo tema ou por um trecho do enunciado. Cada questão já vem com resolução comentada e a análise de cada alternativa.
Professor: monte a prova com questões como esta, com gabarito e folha de respostas, em 30 segundos. Ver planos · Blog