Considere a recorrência T(n) = 3·T(n/3) + c·n para c>0, que descreve o tempo de um algoritmo recursivo. Qual é…
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 a recorrência T(n) = 3·T(n/3) + c·n para c>0, que descreve o tempo de um algoritmo recursivo. Qual é a ordem assintótica do tempo de execução?
- A) T(n log log n), refletindo mais sobre o tempo de execução.
- B) T(n log n)
- C) T(log n), já que a divisão de n diminui rapidamente.
- D) T(n²), devido ao número de chamadas recursivas.
- E) T(n), pois a complexidade é linear pela definição da função.
✅ Resposta correta: alternativa B
Resolução passo a passo
- Identifique os parâmetros da recorrência T(n) = a·T(n/b) + f(n), com a = 3, b = 3 e f(n) = c·n.
- Calcule o expoente crítico log_b(a) = log_3(3) = 1. Logo n^(log_b a) = n.
- Compare f(n) = c·n com n^1. Como f(n) é da mesma ordem de n^1 (caso 2 do Teorema Mestre, com f(n) = Θ(n^(log_b a))), a solução é T(n) = Θ(n log n).
- Verifique por expansão (árvore de recursão). Em cada nível i há 3^i subproblemas de tamanho n/3^i, cada um com custo c·n/3^i. O custo por nível é 3^i · c·n/3^i = c·n, constante. Como a recursão tem aproximadamente log_3 n níveis, o custo total é c·n·log_3 n, que é Θ(n log n).
- Por que as outras estão erradas: A) n log log n cresce mais devagar que n log n, o que não corresponde ao custo por nível constante; C) T(log n) é impossível, pois o próprio trabalho c·n de dividir e combinar já é linear em n; D) n^2 seria o resultado se o custo por nível crescesse, mas aqui o número de subproblemas é compensado pelo tamanho menor de cada um; E) T(n) ignora que a recursão faz log n níveis de trabalho linear, somando mais que n.
- Conclusão: a ordem assintótica é Θ(n log n), alternativa B, que coincide com o gabarito oficial.
💡 Dica: Aplique o Teorema Mestre para resolver a recorrência.
Alternativa por alternativa
O aluno acredita que o log aparece como log log n, talvez confundindo a profundidade da recursão com uma segunda divisão logarítmica dentro do logaritmo.
Pelo Teorema Mestre, com a=3 e b=3 temos n^{log_b a}=n. Isso configura o caso em que T(n)=T(n log n).
O aluno acha que, como o problema é dividido a cada chamada, o tempo total cai para logarítmico, ignorando que o trabalho c·n em cada nível se soma.
O aluno supõe que o número crescente de chamadas recursivas (3 por nível) implica custo quadrático, sem considerar que cada subproblema é três vezes menor.
Por que engana: Confundir a complexidade de tempo com a quantidade de chamadas recursivas, levando a uma escolha incorreta da ordem assintótica.
O aluno confunde a forma da função de custo local c·n com o custo total, achando que a recorrência se resolve diretamente como linear.
Raio-X da questão
ordem assintótica de recorrência
avaliacao
análise de algoritmos · recursão em algoritmos
Revisar o Teorema Mestre e suas aplicações em recorrências.
Confundir a complexidade de tempo com a quantidade de chamadas recursivas, levando a uma escolha incorreta da ordem assintótica.
ciencia_tecnologia
pensamento_critico
cientifico
Questões parecidas com resolução
- Um sistema portátil registra a corrente gerada em um eletrodo de trabalho durante um pulso de 4 segundos. Para comparar…
- Em um protótipo computacional que monitora a salinidade de um tanque, dois eletrodos ficam imersos na água e são usados…
- Em uma lavanderia, uma pessoa instala dois eletrodos próximos ao piso, ligados a uma entrada digital de um controlador…
- Em uma demonstração de interface cérebro-computador, eletrodos colocados sobre o couro cabeludo captam sinais elétricos…
- Em um protótipo de interface computacional controlada por sinais musculares, cada canal utiliza um eletrodo para captar…
- Em uma prótese controlada por sinais musculares, eletrodos na pele captam a atividade elétrica e a enviam ao sistema…
🔎 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