Um algoritmo percorre um vetor de n números e soma seus elementos uma única vez. Qual é a complexidade…
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 um vetor de n números e soma seus elementos uma única vez. Qual é a complexidade temporal desse algoritmo em função de n?
- A) O(log n) — tempo logarítmico, como se o vetor fosse dividido por dois a cada soma.
- B) O(1) — tempo constante, pois ao somar não depende do número de elementos.
- C) O(n log n) — como ordenar antes de somar elementos, aumentando a complexidade.
- D) O(n) — tempo linear.
- E) O(n²) — tempo quadrático, como a soma de elementos de um vetor nunca pode ser linear.
✅ Resposta correta: alternativa D
Resolução passo a passo
- O algoritmo percorre um vetor de n números e soma cada elemento exatamente uma vez. Isso significa que o número de operações cresce na mesma proporção que n.
- Se o vetor tiver 10 elementos, serão cerca de 10 somas; se tiver 1000, cerca de 1000 somas. Dobrar n dobra o trabalho, que é o comportamento de uma complexidade linear.
- Portanto a complexidade temporal é O(n), alternativa D, que é o gabarito oficial.
- A alternativa A está errada, pois O(log n) exigiria dividir o problema pela metade a cada passo, e o enunciado diz que cada elemento é somado uma única vez.
- A alternativa B está errada, pois O(1) significa tempo fixo, independente de n, o que não ocorre, já que mais elementos exigem mais somas.
- A alternativa C está errada, pois o enunciado não menciona ordenação; sem ordenar, não há o termo n log n.
- A alternativa E está errada, pois O(n²) apareceria em laços aninhados, e aqui há apenas um percurso sobre o vetor.
💡 Dica: Considere a definição de complexidade temporal para algoritmos.
Alternativa por alternativa
O aluno associa qualquer algoritmo que trabalha sobre um vetor a buscas binárias, imaginando que o vetor é dividido ao meio a cada passo.
O aluno acredita que a soma de um número é uma operação instantânea e ignora que cada elemento do vetor precisa ser visitado.
O aluno confunde a soma com a ordenação, assumindo que algum passo de ordenação está embutido no algoritmo, mesmo sem o enunciado mencionar isso.
Por que engana: Confundir a complexidade de somar elementos com a de ordenar, escolhendo O(n log n) ao invés de O(n).
Cada elemento é visitado uma vez; o número de operações cresce proporcionalmente a n, caracterizando tempo linear.
O aluno supõe que qualquer operação sobre um vetor exige comparar todos os pares de elementos, como em laços aninhados, e não percebe que há um único percurso.
Raio-X da questão
complexidade temporal
avaliacao
complexidade de algoritmos · análise de desempenho
Revisar conceitos de complexidade de algoritmos e notação Big O.
Confundir a complexidade de somar elementos com a de ordenar, escolhendo O(n log n) ao invés de O(n).
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Em um programa, um laço for percorre todos os n elementos de um vetor. Em cada repetição, o programa atualiza uma…
- Considere o algoritmo in-place que calcula somas prefixadas em um vetor A[0..n-1]: para i de 1 até n-1 faça A[i] ? A[i]…
- Explique como funciona um algoritmo que utiliza repetição simples para calcular a soma de números consecutivos de 1 a n…
- Defina a assinatura (nome e parâmetros) de um algoritmo que recebe uma coleção de números e uma variável n (parâmetro) e…
- Dado um vetor 'valores' com N inteiros, descreva o algoritmo e a estrutura de dados mais simples para calcular soma e…
- Qual o algoritmo correto para somar números inteiros até 10?
🔎 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