Considere dois algoritmos para processar n registros: A tem complexidade O(n log n) e B tem O(n). Para valores…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Construir soluções computacionais de problemas de diferentes áreas do conhecimento, de forma individual e colaborativa, selecionando as estruturas de dados e técnicas adequadas, aperfeiçoando e articulando saberes escolares.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Considere dois algoritmos para processar n registros: A tem complexidade O(n log n) e B tem O(n). Para valores grandes de n, qual algoritmo terá menor crescimento do tempo de execução?
- A) Ambos terão o mesmo tempo de execução para grandes n.
- B) O algoritmo B é inválido e não pode ser executado.
- C) O algoritmo A será mais eficiente em listas pequenas.
- D) O algoritmo A será mais rápido, pois log n cresce lentamente.
- E) O algoritmo B (O(n)) terá menor crescimento assintótico do tempo de execução.
✅ Resposta correta: alternativa E
Resolução passo a passo
- Identifique o que a questão pede: qual dos dois algoritmos cresce menos no tempo de execução quando n é grande.
- A complexidade O(n log n) cresce mais rápido que O(n), pois é o produto de n por log n, e log n cresce sem limite à medida que n aumenta.
- Na comparação assintótica, o fator log n faz o algoritmo A crescer mais que linearmente, enquanto B cresce de forma linear, que é o menor crescimento entre os dois.
- Logo, a alternativa E está correta: o algoritmo B, de complexidade O(n), tem menor crescimento assintótico.
- Por que as outras estão erradas: A afirma que ambos têm o mesmo tempo, o que contraria a diferença entre n log n e n; B diz que o algoritmo B é inválido, sem qualquer base no enunciado; C fala em eficiência para listas pequenas, que não é o foco da pergunta sobre valores grandes de n; D afirma que A é mais rápido, o que é falso, pois log n faz A crescer mais que B.
💡 Dica: Compare as complexidades dos algoritmos A e B.
Alternativa por alternativa
Acredita que as diferenças entre O(n log n) e O(n) desaparecem para n grande, tratando as duas complexidades como equivalentes.
Confunde a notação de complexidade com validade do algoritmo, imaginando que uma complexidade O(n) signifique que o algoritmo não pode ser executado.
Foca em desempenho em listas pequenas, ignorando que a pergunta trata do comportamento para valores grandes de n, onde a análise assintótica é decisiva.
Interpreta que log n cresce lentamente e por isso torna o algoritmo A mais rápido, esquecendo que o fator log n ainda aumenta o tempo em relação a um crescimento linear puro.
Por que engana: Confundir a eficiência de algoritmos de complexidade O(n log n) com O(n), acreditando que ambos têm o mesmo desempenho em grandes entradas.
Termos assintóticos indicam comportamento para entradas grandes; O(n) cresce linearmente enquanto O(n log n) cresce mais rápido devido ao fator log n, tornando O(n) assintoticamente mais eficiente.
Raio-X da questão
complexidade de algoritmos
avaliacao
complexidade de algoritmos · análise de desempenho
Revisar conceitos de complexidade de algoritmos e suas notações.
Confundir a eficiência de algoritmos de complexidade O(n log n) com O(n), acreditando que ambos têm o mesmo desempenho em grandes entradas.
ciencia_tecnologia
pensamento_critico
cientifico
Questões parecidas com resolução
- Tabela de tempos de execução (s): Entrada pequena — A:0,2 B:0,4; Entrada média — A:1,1 B:0,9; Entrada grande — A:5,6…
- Em um projeto de monitoramento de rios, uma boia computacional organiza leituras de sensores antes de enviá-las por…
- 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…
- Em uma competição, dois alunos criaram algoritmos para resolver o mesmo problema. Os dois usaram o mesmo tipo de passo…
- Em um exercício de preparação para períodos de chuva intensa, uma central municipal de Defesa Civil precisa localizar…
- Câmeras instaladas em uma via movimentada registram o fluxo de veículos para ajustar o tempo dos semáforos. Dois…
🔎 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