Para um algoritmo que percorre um vetor dados de tamanho N verificando cada elemento até achar um alvo, qual a…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Construir e simular algoritmos, de forma independente ou em colaboração, que resolvam problemas simples e do cotidiano com uso de sequências, seleções condicionais e repetições de instruções.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Para um algoritmo que percorre um vetor dados de tamanho N verificando cada elemento até achar um alvo, qual a complexidade temporal no pior caso em notação Big O?
- A) O(N^2).
- B) O(1).
- C) O(N).
- D) O(N log N).
- E) O(log N).
✅ Resposta correta: alternativa C
Resolução passo a passo
- Entenda o algoritmo descrito: ele percorre o vetor dados, de tamanho N, verificando cada elemento em sequência até encontrar o alvo. Esse é o método de busca linear.
- Pense no pior caso, que acontece quando o alvo está na última posição ou não está no vetor. Nesse caso, o algoritmo precisa visitar todos os N elementos, uma vez cada.
- Como o número de comparações cresce proporcionalmente ao tamanho N do vetor, a complexidade temporal no pior caso é O(N), que é linear.
- Verificando as outras alternativas: A) O(N^2) estaria errada, pois exigiria um laço aninhado, o que não ocorre em uma varredura simples. B) O(1) estaria errada, pois o tempo não é constante, já que depende do tamanho do vetor. D) O(N log N) estaria errada, pois é típica de algoritmos de ordenação eficientes, não de uma busca simples. E) O(log N) estaria errada, pois é típica da busca binária, que exige vetor ordenado e descarta metade dos elementos a cada passo.
- Conclusão: a alternativa correta é a C, O(N), que coincide com o gabarito oficial.
💡 Dica: Considere a definição de complexidade de algoritmos.
Alternativa por alternativa
O aluno supõe que qualquer percurso sobre o vetor exige comparações aninhadas, confundindo uma varredura simples com um laço duplo.
O aluno acredita que encontrar o alvo é imediato, pensando apenas no melhor caso ou em acesso direto a um elemento, em vez do pior caso da varredura.
No pior caso o algoritmo verifica cada um dos N elementos uma vez; cada verificação é operação de tempo constante, resultando em tempo linear O(N).
O aluno associa qualquer algoritmo sobre N elementos ao custo N log N, típico de ordenações, sem analisar o procedimento descrito.
O aluno confunde a busca linear com a busca binária, assumindo divisão do espaço de busca a cada passo, o que exige vetor ordenado e não se aplica aqui.
Por que engana: Confundir a complexidade de busca linear com a de busca binária, escolhendo O(log N) em vez de O(N).
Raio-X da questão
complexidade temporal
avaliacao
notação Big O · análise de algoritmos
Revisar notação Big O e complexidade de algoritmos.
Confundir a complexidade de busca linear com a de busca binária, escolhendo O(log N) em vez de O(N).
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Dado um vetor (array) não ordenado com n elementos, qual é a complexidade temporal, no pior caso, do algoritmo que…
- Considere um algoritmo que para cada um dos N elementos de um vetor executa, no pior caso, uma busca linear sobre M…
- Qual é a complexidade temporal do algoritmo Bubble Sort no pior caso?
- Se uma matriz n × n contém registros e um algoritmo compara cada par distinto de elementos para detectar duplicidade de…
- Num algoritmo de ordenação que usa dois índices em laços aninhados para percorrer um vetor de N nomes, como a variável N…
- Um algoritmo percorre um vetor de n números e soma seus elementos uma única vez. Qual é a complexidade temporal desse…
🔎 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