Considere um algoritmo que para cada um dos N elementos de um vetor executa, no pior caso, uma busca linear…
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
Considere um algoritmo que para cada um dos N elementos de um vetor executa, no pior caso, uma busca linear sobre M itens. Qual é a complexidade temporal assintótica em função de N e M?
- A) O(N·M) — tempo proporcional a N vezes M.
- B) O(M) — linear em relação ao número de itens apenas.
- C) O(N^2) — quadrática em relação ao número de elementos.
- D) O(N + M) — soma da quantidade de elementos.
- E) O(N^M) — exponencial com base em M.
✅ Resposta correta: alternativa A
Resolução passo a passo
- Identifique a estrutura do algoritmo. Há um laço externo que percorre os N elementos do vetor e, para cada um deles, uma busca linear que, no pior caso, examina todos os M itens.
- Calcule o custo de uma busca linear isolada. No pior caso ela percorre os M itens, logo custa O(M).
- Como essa busca é repetida N vezes, o custo total é a soma de N execuções de O(M), isto é, N vezes M operações no pior caso.
- Logo a complexidade temporal assintótica é O(N·M), alternativa A, que coincide com o gabarito oficial.
- Por que as outras estão erradas: B ignora completamente o laço externo sobre os N elementos; C supõe que M é igual a N, o que não é dado no enunciado; D trata as duas repetições como soma, quando elas estão aninhadas e precisam ser multiplicadas; E confunde um laço aninhado com um crescimento exponencial, que não ocorre aqui.
💡 Dica: Analise a relação entre N e M na busca linear.
Alternativa por alternativa
Para cada um dos N elementos realiza-se até M comparações; operações aninhadas multiplicam, resultando em N vezes M passos no pior caso.
O aluno considera apenas a busca linear sobre os M itens e esquece que ela é repetida para cada um dos N elementos do vetor.
O aluno assume que o tamanho da busca é igual ao número de elementos N, transformando o enunciado em um caso quadrático com uma única variável.
O aluno soma os custos das duas partes em vez de multiplicá-los, tratando laços aninhados como se fossem sequenciais.
Por que engana: Confundir a complexidade de busca linear com a complexidade total do algoritmo, levando a uma resposta incorreta sobre a relação entre N e M.
O aluno confunde uma repetição aninhada de tamanho M com crescimento exponencial, achando que M no expoente é a forma correta de representar o custo.
Raio-X da questão
complexidade temporal
avaliacao
complexidade de algoritmos · busca linear
Revisar conceitos de complexidade de algoritmos e busca linear.
Confundir a complexidade de busca linear com a complexidade total do algoritmo, levando a uma resposta incorreta sobre a relação entre N e M.
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