Em uma atividade de análise de algoritmos, uma turma usa a função recursiva count_occurrences(L, x) para…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Elaborar algoritmos que envolvam instruções sequenciais, de repetição e de seleção usando uma linguagem de programação.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Em uma atividade de análise de algoritmos, uma turma usa a função recursiva count_occurrences(L, x) para contar quantas vezes o valor x aparece em uma lista L. A função é definida assim: se L estiver vazia, retorna 0; caso contrário, verifica se L[0] é igual a x e soma 1 ou 0 ao resultado de count_occurrences(L[1:], x). Considere que L[1:] cria uma nova lista, copiando todos os elementos a partir da segunda posição, que essa cópia leva tempo proporcional ao número de elementos copiados e que as demais operações realizadas em cada chamada levam tempo constante. Seja n o tamanho inicial de L. Com base nessas informações, qual é a complexidade temporal, em função de n, da execução de count_occurrences(L, x) no pior caso?
- A) O(log n) — logarítmica no tamanho inicial da lista.
- B) O(1) — constante no tamanho inicial da lista.
- C) O(n log n) — quase linear no tamanho inicial da lista.
- D) O(n²) — quadrática no tamanho inicial da lista.
- E) O(n³) — cúbica no tamanho inicial da lista.
✅ Resposta correta: alternativa D
Resolução passo a passo
- Identifique o custo de uma única chamada. Em cada chamada, a função faz operações de tempo constante (verificar se a lista está vazia, comparar L[0] com x e somar 0 ou 1), mas também executa L[1:], que copia todos os elementos restantes da lista. Se a lista atual tem k elementos, essa cópia custa proporcional a k - 1. Passo 2: Acompanhe a sequência de chamadas. A primeira chamada recebe n elementos e copia n - 1. A segunda recebe n - 1 elementos e copia n - 2. Isso continua até a lista ficar vazia. Passo 3: Some os custos das cópias. O total é (n - 1) + (n - 2) + ... + 1 + 0 = n(n - 1)/2, que é igual a (n^2 - n)/2. Passo 4: Simplifique. Descartando o termo de menor grau e a constante 1/2, o custo total cresce com n^2, logo a complexidade no pior caso é O(n^2). O pior caso ocorre quando x não aparece na lista ou aparece só no final, pois a recursão percorre todos os elementos de qualquer forma. Passo 5: Compare com as alternativas. A alternativa A está errada, pois não há divisão do problema pela metade como na busca binária. A alternativa B está errada, pois ignora o custo linear de cada cópia. A alternativa C está errada, pois n log n corresponde a algoritmos como o mergesort, que não é o padrão desta recursão. A alternativa E está errada, pois não existe um terceiro nível de trabalho que multiplique as cópias; o custo total é uma soma de termos lineares, não um produto. O gabarito oficial D está correto.
💡 Dica: Analise a estrutura do algoritmo e a relação com o tamanho da lista.
Alternativa por alternativa
Acredita que a recursão reduz o problema pela metade a cada passo, como na busca binária, e por isso associa a complexidade a log n. Aqui cada chamada remove apenas um elemento.
Por que engana: Confundir a complexidade do algoritmo, acreditando que a recursão gera um aumento quadrático no tempo de execução.
Considera que cada chamada é uma operação de tempo constante e ignora que L[1:] copia a lista inteira. O enunciado diz explicitamente que essa cópia custa tempo proporcional ao número de elementos.
Associa a recursão que divide e combina a algoritmos como mergesort e supõe um custo n log n. Essa função não divide a lista ao meio; ela descarta um elemento por vez.
A função realiza aproximadamente n chamadas recursivas. Na chamada que recebe uma lista de tamanho k, a operação L[1:] copia k − 1 elementos e, portanto, custa O(k). O custo total é proporcional a (n − 1) + (n − 2) + ... + 1, cuja soma é n(n − 1)/2. Assim, a complexidade temporal é O(n²).
Imagina que o custo de cada nível se multiplica pelos demais e que há três fatores de custo quadrático ou linear encadeados. Na realidade, os custos das cópias se somam, formando uma soma de termos lineares.
Raio-X da questão
complexidade de algoritmos
avaliacao
análise de algoritmos · recursão
Revisar conceitos de complexidade temporal de algoritmos recursivos.
Confundir a complexidade do algoritmo, acreditando que a recursão gera um aumento quadrático no tempo de execução.
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Considere um algoritmo recursivo que percorre uma lista L de n elementos, fazendo uma chamada recursiva por elemento e…
- Em pseudocódigo, ao implementar um algoritmo recursivo que percorre uma lista L processando exatamente um elemento por…
- Dado um vetor (array) não ordenado com n elementos, qual é a complexidade temporal, no pior caso, do algoritmo que…
- Em pseudocódigo, qual deve ser o caso base de um algoritmo recursivo que conta elementos de uma lista L (variável L)…
- Considere o pseudocódigo: for i from 1 to n: for j from 1 to n: if A[i] == A[j] then count ? count + 1. Qual é a…
- Escreva em pseudocódigo um algoritmo recursivo count_pares(L) que recebe uma lista L de inteiros e retorna a quantidade…
🔎 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