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
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
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.
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.
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.
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.
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
complexidade de algoritmos
avaliacao
complexidade de algoritmos · análise de loops
Revisar conceitos de complexidade temporal de algoritmos.
Confundir a complexidade de um algoritmo aninhado, acreditando que é cúbica ao invés de quadrática.
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Uma equipe precisa gerar cem relatórios com a mesma estrutura, mudando apenas os valores das turmas e das notas. — Qual…
- No fim de semana da feira de ciências do bairro, a equipe de organização percebeu um problema repetido: dezenas de…
- Projete um algoritmo guloso em pseudocódigo que, dado um vetor de n intervalos [inicio, fim], selecione o maior conjunto…
- Projete em pseudocódigo uma função recursiva quicksort(L) que ordena uma lista L de inteiros em ordem não crescente…
- Projete uma função recursiva em pseudocódigo flatten(L) que recebe uma lista L que pode conter inteiros e sublistas…
- Em um algoritmo, uma função recebe um vetor chamado dados que não deve ser alterado. Para garantir que a variável…
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