Um algoritmo percorre uma lista de n elementos com dois loops aninhados: para i de 1 a n: para j de 1 a n…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Identificar o comportamento dos algoritmos no que diz respeito ao consumo de recursos como tempo de execução, espaço de memória e energia, entre outros.
Fonte: Base Nacional Comum Curricular (MEC).Questã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 operação constante. Qual a complexidade temporal em notação Big-O do algoritmo em função de n?
- A) O(n^3) — imaginar um terceiro loop.
- B) O(n^2)
- C) O(log n) — pensa em divisão por dois.
- D) O(n!) — confundindo com permutações.
- E) O(n) — complexidade linear.
✅ Resposta correta: alternativa B
Resolução passo a passo
- O loop externo (variável i) roda de 1 a n, ou seja, n vezes.
- Para cada valor de i, o loop interno (variável j) também roda de 1 a n, ou seja, n vezes.
- O número total de execuções da operação constante é n vezes n, isto é, n^2.
- Descartando a constante multiplicativa (no caso, 1) e termos de ordem menor, a complexidade temporal em Big-O é O(n^2), alternativa B, que coincide com o gabarito oficial.
- A alternativa A está errada porque só há dois loops, não três, então o expoente seria 2 e não 3. A alternativa C está errada porque complexidade logarítmica exige que o tamanho do problema seja dividido a cada passo, o que não ocorre aqui. A alternativa D está errada porque O(n!) surge em algoritmos que geram todas as permutações, o que não é descrito. A alternativa E está errada porque complexidade linear exigiria um único loop de n passos, e aqui o trabalho cresce com o quadrado de n.
💡 Dica: Analise a estrutura dos loops para determinar a complexidade.
Alternativa por alternativa
Acredita que cada loop aninhado adiciona um fator n, e imagina um terceiro loop que não existe no enunciado.
Por que engana: Confundir a complexidade de algoritmos com a adição de um loop extra, resultando em O(n^3).
Cada iteração do loop externo aciona n iterações do loop interno, totalizando aproximadamente n × n operações, caracterizando ordem quadrática.
Associa qualquer algoritmo com repetição a divisão do problema pela metade, típico da busca binária, sem verificar se o tamanho diminui a cada passo.
Confunde loops aninhados com geração de todas as permutações dos elementos, que de fato cresce com n!.
Entende que, como a lista tem n elementos, a complexidade é sempre linear, ignorando que o loop interno é repetido para cada iteração do externo.
Raio-X da questão
complexidade de algoritmos
avaliacao
notação Big-O · loops aninhados
Revisar a notação Big-O e como calcular a complexidade de algoritmos.
Confundir a complexidade de algoritmos com a adição de um loop extra, resultando em O(n^3).
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Considere um algoritmo com duas estruturas de repetição aninhadas, cada uma iterando de 1 até n. Qual é a complexidade…
- 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…
- 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…
- 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…
🔎 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