Considere um algoritmo com duas estruturas de repetição aninhadas, cada uma iterando de 1 até n. Qual é a…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Construir e simular algoritmos, de forma independente ou em colaboração, que resolvam problemas simples e do cotidiano com uso de sequências, seleções condicionais e repetições de instruções.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Considere um algoritmo com duas estruturas de repetição aninhadas, cada uma iterando de 1 até n. Qual é a complexidade de tempo em notação O(n) desse algoritmo?
- A) O(n^3), porque há uma quantidade de loops.
- B) O(n^2).
- C) O(log n), pois a consulta é mais eficiente.
- D) O(n^2 + n), pois é uma soma de complexidade.
- E) O(n), pois há apenas um looping principal.
✅ Resposta correta: alternativa B
Resolução passo a passo
- Cada estrutura de repetição vai de 1 até n, então o laço externo executa n vezes.
- Para cada execução do laço externo, o laço interno também executa n vezes, pois está aninhado dentro dele.
- O número total de execuções do corpo mais interno é n multiplicado por n, ou seja, n^2.
- Na notação O, descartamos constantes e termos de menor crescimento, então a complexidade é O(n^2).
- Por que as outras estão erradas. A) O(n^3) exigiria três laços aninhados, e a questão descreve apenas dois. C) O(log n) é típico de algoritmos que dividem o problema pela metade, como a busca binária, e não de laços aninhados. D) O(n^2 + n) é uma forma não simplificada, pois o termo n é dominado por n^2 e a notação padrão usa a forma mais simples. E) O(n) valeria para um único laço, mas o enunciado tem laços aninhados.
- Observação: o enunciado pede a complexidade 'em notação O(n)', o que é confuso, pois a resposta correta é O(n^2), que é a notação O aplicada a esse algoritmo. Por isso a alternativa B é a correta, e o gabarito está coerente com essa leitura.
💡 Dica: Analise a estrutura de repetição para determinar a complexidade.
Alternativa por alternativa
O aluno acha que cada laço aninhado multiplica a complexidade por n, mas conta um laço a mais do que o enunciado descreve. Também pode confundir quantidade de laços com ordem de crescimento.
Por que engana: Confundir a complexidade de um algoritmo com múltiplos loops como O(n^3) ao invés de O(n^2).
Duas estruturas aninhadas que iteram n vezes realizam aproximadamente n × n = n^2 iterações; termos de menor ordem são desprezados na notação O.
O aluno associa qualquer algoritmo eficiente ou qualquer consulta a O(log n), como na busca binária, sem analisar a estrutura de repetição apresentada.
O aluno soma as complexidades dos dois laços como se fossem blocos sequenciais, mas aqui eles estão aninhados, o que resulta em multiplicação. Além disso, não reduz o termo n, que é dominado por n^2.
O aluno considera apenas o laço externo como 'principal' e ignora o laço interno, tratando o aninhamento como se fosse um único laço.
Raio-X da questão
complexidade de algoritmos
avaliacao
notação de complexidade · estruturas de repetição
Revisar conceitos de complexidade de tempo e estruturas de repetição.
Confundir a complexidade de um algoritmo com múltiplos loops como O(n^3) ao invés de O(n^2).
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Um algoritmo percorre uma lista de n elementos com dois loops aninhados: para i de 1 a n: para j de 1 a n: executar…
- Um algoritmo aninhado percorre uma matriz M de tamanho n×n com dois loops: para i de 1 até n e para j de 1 até n. Se a…
- Qual é a complexidade temporal, em notação O, do algoritmo clássico que multiplica duas matrizes quadradas n×n usando…
- Um algoritmo compara cada par distinto de n elementos (dois laços aninhados com i<j). Em função de n, quantas…
- Um algoritmo apresenta loops aninhados: para i de 1 até m faça para j de 1 até n faça executar_acao; fim para; fim para…
- Considere o pseudocódigo: for i from 1 to n: for j from 1 to n: if A[i] == A[j] then count ? count + 1. Qual é a…
🔎 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