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
- Na horta da escola, um painel deve avisar enquanto a umidade do solo estiver abaixo de 50. O programa usado no painel é…
- Em uma apresentação escolar, o programa de luzes deve ativar efeitos nas cinco cenas, numeradas de 1 a 5. O trecho usado…
- Quando o rio se aproxima das casas, a Defesa Civil de um município usa um programa para avisar os moradores pelo…
- Por que o painel de alerta do rio não envia aviso mesmo quando o nível sobe em duas medições seguidas? Em uma simulação…
- — O painel marcou 80%, mas o caminhão não recebeu o aviso de retirada — observou a responsável pelo ponto de coleta de…
- — A última peça nunca aparece no painel — disse a monitora do centro cultural, ao conferir o inventário digital de…
🔎 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