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
- Em um projeto de monitoramento de rios, uma boia computacional organiza leituras de sensores antes de enviá-las por…
- Uma biblioteca escolar recebeu caixas de livros doados para uma feira de troca. Para registrar os exemplares, a equipe…
- Um centro cultural público oferece inscrições on-line para atividades com critérios variados. Na oficina de teatro…
- Uma escola está testando dois protótipos de aplicativo para que estudantes consultem mudanças de sala, horários e…
- Uma secretaria municipal de educação está digitalizando pedidos de transporte escolar e de atendimento em contraturno…
- — O cartaz não pode sair duas vezes, pois a feira começa em uma hora — alertou a coordenadora do centro cultural. No…
🔎 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