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
- Os aplicativos de mapa, como o GPS, ajudam o carro de entregas a chegar à casa do cliente. O aplicativo compara dois…
- Lia organiza carrinhos, bonecas e blocos separando cada tipo, colocando-os em caixas e guardando as caixas na…
- Em um jogo, uma personagem controlada por IA precisa chegar a um tesouro sem bater nas paredes. Qual instrução ajuda a…
- Desenhe um algoritmo em pseudocódigo que, dada uma matriz M[N][M] com 0 (livre) e 1 (bloqueado), identifique todas as…
- Em um programa, Substring(codigo, início, quantidade) pega letras do texto a partir da posição indicada, e…
- Projete um algoritmo em pseudocódigo que, dadas as variáveis temperatura (inteiro ºC), ocupacao (inteiro, número 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