Qual das assertivas abaixo descreve corretamente o propósito da memoização?
Resposta correta: B) Memoização armazena resultados para evitar recomputar subproblemas repetidos, reduzindo o tempo de execução.
Observação: a memoização acelera recursões que geram muitas subChamadas repetidas, ao custo de consumir memória para armazenar os resultados.
Qual é a principal desvantagem da implementação recursiva simples para o cálculo da sequência de Fibonacci?
Resposta correta: B) A principal desvantagem da recursão para Fibonacci é o tempo de execução exponencial devido à recomputação de subproblemas.
Comentário: sem memoização, muitas chamadas repetem os mesmos cálculos, levando a crecimiento exponencial do tempo.
Como a memoização afeta a complexidade de tempo e espaço da solução recursiva para o problema de Fibonacci?
Resposta correta: A) A memoização reduz o tempo de execução, mas consome memória extra; para Fibonacci, a solução costuma ter tempo O(N) com memória O(N).
Observação: o ganho de tempo depende da duplicação de subproblemas; memoização evita essa duplicação.
Considere a implementação recursiva ingênua de Fibonacci e a mesma implementação com memoização. Assinale a alternativa que apresenta corretamente as ordens de crescimento de tempo (e, quando aplicável, de memória) de cada abordagem.
Resposta correta: A) Recursiva: O(2^N) e Memoização: O(N) de tempo (com memória O(N)).
Justificativa: para fibonnaci simples sem memoização, o número de chamadas cresce exponencialmente; com memoização, cada F(k) é calculado uma vez, resultando em tempo linear em N, com uso adicional de memória.