A memomosização aumenta drasticamente a eficiência dos algoritmos de programação dinâmica, evitando cálculos redundantes. A programação dinâmica resolve problemas, dividindo -os em subproblemas menores, resolvendo cada subproblema apenas uma vez e armazenando suas soluções. A memórias é uma abordagem de cima para baixo para conseguir isso.
Aqui está como funciona:
1.
Estrutura recursiva: Problemas de programação dinâmica geralmente se prestam a soluções recursivas. Uma implementação recursiva ingênua calcularia repetidamente as soluções para os mesmos subproblemas, levando à complexidade do tempo exponencial.
2.
armazenando resultados: A memórias introduz uma estrutura de dados (geralmente uma tabela ou matriz de hash) para armazenar as soluções para os subproblemas já calculados. Essa estrutura é frequentemente chamada de "memorando" ou "cache".
3.
verificando o memorando: Antes de resolver recursivamente um subproblema, o algoritmo primeiro verifica o memorando. Se a solução já estiver presente (o que significa que o subproblema já foi resolvido antes), ela foi recuperada diretamente do memorando, evitando a recomputação.
4.
armazenando o resultado: Se a solução não for encontrada no memorando, o algoritmo resolve recursivamente o subproblema e depois * armazena * o resultado no memorando antes de devolvê -lo.
Exemplo: Considere o cálculo da sequência de Fibonacci. Uma abordagem recursiva ingênua tem complexidade exponencial porque recalcula muitos números de Fibonacci várias vezes. Com memórias:
`` `Python
memorando ={} # inicialize o memorando
def fibonacci_memo (n):
Se n em memorando:
Retornar memorando [n] # Recuperar do memorando se já calculado
Se n <=1:
retornar n
outro:
resultado =fibonacci_memo (n-1) + fibonacci_memo (n-2)
memorando [n] =resultado # Armazene o resultado no memorando
resultado de retorno
Imprimir (Fibonacci_memo (5)) # saída:5
`` `
Neste exemplo, `Memo` armazena os números de fibonacci computados. Quando `fibonacci_memo (5)` é chamado, ele chama recursivamente `fibonacci_memo (4)` e `fibonacci_memo (3)`. `fibonacci_memo (3)` vai ligar recursivamente `fibonacci_memo (2)` e `fibonacci_memo (1)`. No entanto, uma vez que `fibonacci_memo (1)` ou `fibonacci_memo (2)` é calculado e armazenado em 'memorando', as chamadas subsequentes para esses mesmos subproblemas retornarão diretamente os resultados armazenados, evitando a computação redundante. Isso reduz a complexidade do tempo da exponencial a linear.
Em essência, a memórias transforma um algoritmo recursivo potencialmente exponencial em um algoritmo de tempo linear (ou tempo polinomial em outros casos), alavancando o poder dos resultados previamente calculados. É uma poderosa técnica de otimização frequentemente usada em conjunto com a programação dinâmica para melhorar a eficiência.
