Dado um vetor (array) não ordenado com n elementos, qual é a complexidade temporal, no pior caso, do algoritmo…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Criar soluções de problemas para os quais seja adequado o uso de registros e matrizes unidimensionais para descrever suas informações e automatizá-las usando uma linguagem de programação.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Dado um vetor (array) não ordenado com n elementos, qual é a complexidade temporal, no pior caso, do algoritmo que realiza busca linear para verificar se um dado x está presente na lista?
- A) Complexidade O(n^2): cada elemento é comparado com todos os outros.
- B) Complexidade O(n log n): a busca envolve ordenação implícita antes da verificação.
- C) Complexidade O(1): busca linear encontra x em tempo constante.
- D) Complexidade O(log n): divisão e conquista reduz o número de comparações.
- E) O(n) no pior caso.
✅ Resposta correta: alternativa E
Resolução passo a passo
- Na busca linear, percorremos o vetor do início ao fim, comparando x com cada elemento até encontrá-lo ou esgotar a lista.
- No pior caso, x não está presente ou está na última posição, então todos os n elementos são comparados uma vez cada.
- Como o número de comparações cresce linearmente com n, a complexidade temporal no pior caso é O(n).
- A alternativa E está correta e coincide com o gabarito oficial.
- A alternativa A está errada, pois O(n^2) apareceria em algoritmos como a comparação de todos os pares, o que não ocorre na busca linear, que faz uma única passada.
- A alternativa B está errada, pois a busca linear não ordena o vetor; o n log n corresponde à ordenação eficiente, não à busca sequencial.
- A alternativa C está errada, pois O(1) exigiria acesso direto ao elemento procurado, o que não é possível sem informação adicional sobre a posição de x em um vetor não ordenado.
- A alternativa D está errada, pois O(log n) é típico da busca binária, que exige vetor ordenado e divide o espaço de busca pela metade; a busca linear não faz essa divisão.
💡 Dica: Considere a definição de complexidade temporal de algoritmos.
Alternativa por alternativa
O aluno pode ter confundido a busca linear com algoritmos que comparam todos os pares de elementos, como a verificação de duplicatas por força bruta.
O aluno pode ter achado que, por o vetor não estar ordenado, seria necessário ordená-lo antes da busca, associando a complexidade da ordenação eficiente à busca.
Por que engana: Confundir a complexidade da busca linear com a de algoritmos que envolvem ordenação ou divisão e conquista.
O aluno pode ter imaginado que, ao encontrar x, a busca seria imediata, esquecendo que no pior caso x pode estar no fim do vetor ou não existir.
O aluno pode ter confundido a busca linear com a busca binária, aplicando a estratégia de dividir ao meio sem que o vetor esteja ordenado.
A busca linear compara x com cada elemento em sequência; se x estiver ausente ou na última posição, são feitas n comparações, portanto tempo proporcional a n.
Raio-X da questão
complexidade de algoritmos
avaliacao
complexidade de algoritmos · busca linear
Revisar a busca linear e suas características de complexidade.
Confundir a complexidade da busca linear com a de algoritmos que envolvem ordenação ou divisão e conquista.
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Para um algoritmo que percorre um vetor dados de tamanho N verificando cada elemento até achar um alvo, qual a…
- Considere um algoritmo que para cada um dos N elementos de um vetor executa, no pior caso, uma busca linear sobre M…
- Em uma atividade de análise de algoritmos, uma turma usa a função recursiva count_occurrences(L, x) para contar quantas…
- O que caracteriza um algoritmo de busca linear?
- Identifique o algoritmo de busca linear. Qual é sua principal característica em listas?
- Em um algoritmo de busca linear, o que é avaliado em cada iteração?
Todas as questões de Programação - Programação usando registros e matrizes
🔎 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