Computação9º anoBNCC EF69CO04Difícil⏱ medio

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é…

Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva

Habilidade BNCC EF69CO04

Construir soluções de problemas usando a técnica de decomposição e automatizar tais soluções usando uma linguagem de programação.

Fonte: Base Nacional Comum Curricular (MEC).

Questão

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 operação dentro do laço interno tem custo constante, qual é a complexidade temporal desse algoritmo em função de n?

A) O(n³) - a complexidade é cúbica devido à aninhamento.
B) O(n) - a complexidade é linear, não quadrática.
C) O(1) - a complexidade é constante, não depende de n.
D) O(n²)
E) O(n² log n) - envolve log n incorretamente na complexidade.

✅ Resposta correta: alternativa D

Resolução passo a passo

O laço externo (i de 1 até n) executa n vezes.
Para cada valor de i, o laço interno (j de 1 até n) executa n vezes.
Como a operação interna tem custo constante, o total de operações é n vezes n, isto é, n^2.
Portanto a complexidade temporal é O(n^2), alternativa D, que coincide com o gabarito oficial.
A alternativa A está errada, pois O(n^3) exigiria um terceiro laço aninhado, o que não existe aqui.
A alternativa B está errada, pois O(n) corresponderia a um único laço de n passos, e não a dois laços aninhados.
A alternativa C está errada, pois O(1) significaria custo fixo, independente do tamanho da matriz, o que não ocorre já que os laços dependem de n.
A alternativa E está errada, pois não há ordenação ou divisão de problema que justifique o termo log n; os laços são simples contagens.

💡 Dica: Analise a estrutura dos loops para determinar a complexidade.

Alternativa por alternativa

A Erradaerro: Conceituala que mais engana

O aluno acredita que cada laço aninhado multiplica a complexidade por n, somando um fator extra por ter 'aninhamento', como se houvesse três laços.

Por que engana: Confundir a complexidade de um algoritmo aninhado, acreditando que é cúbica ao invés de quadrática.

B Erradaerro: Interpretação

O aluno pensa que, por a matriz ter n elementos, basta percorrer uma única vez, ignorando que o laço interno roda n vezes para cada iteração do externo.

C Erradaerro: Conceitual

O aluno confunde custo constante da operação interna com custo constante do algoritmo inteiro, sem perceber que o número de repetições cresce com n.

D Correta

O laço externo executa n vezes e, a cada iteração, o laço interno executa n vezes, resultando em n·n = n² execuções da operação de custo constante.

E Erradaerro: Senso comum

O aluno associa qualquer aninhamento a algoritmos de ordenação ou divisão e conquista, acrescentando o fator log n sem que ele exista na estrutura do código.

Raio-X da questão

Dificuldade Difícil

Bloom Analisar

Leitura alto

Discriminação alto

Peso pedagógico alto

Autonomia do enunciado completo

Cobertura da habilidade unica

🧪 Simulado🩺 Diagnóstico🧮 Exige cálculo🏠 Cotidiano🔗 Interdisciplinar⭐ Representativa✍️ interpretativa🧩 desafio

🎯 Conceito central

complexidade de algoritmos

📌 Objetivo

avaliacao

🧱 Pré-requisitos

complexidade de algoritmos · análise de loops

📚 Reveja

Revisar conceitos de complexidade temporal de algoritmos.

⚠️ Erro mais comum

Confundir a complexidade de um algoritmo aninhado, acreditando que é cúbica ao invés de quadrática.

🌎 Tema transversal

ciencia_tecnologia

🤝 Socioemocional

pensamento_critico

🏫 Contexto

abstrato

Questões parecidas com resolução

Todas as questões de Estratégias de solução de problemas - Decomposiçã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