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
- Para um algoritmo que percorre um vetor dados de tamanho N verificando cada elemento até achar um alvo, qual a…
- Qual é a complexidade temporal, em notação O, de um algoritmo que percorre todos os elementos de uma matriz de dimensão…
- Dado um vetor (array) não ordenado com n elementos, qual é a complexidade temporal, no pior caso, do algoritmo que…
- Um algoritmo aninhado percorre uma matriz M de tamanho n×n com dois loops: para i de 1 até n e para j de 1 até n. Se a…
- Em uma atividade de organização de dados, duas listas já estão ordenadas em ordem crescente. O algoritmo de merge…
- 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…
🔎 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