A memórias é uma técnica de otimização crucial usada na programação dinâmica para melhorar significativamente a eficiência. Funciona armazenando os resultados de chamadas de função caras e retornando o resultado em cache quando as mesmas entradas ocorrem novamente. Isso evita cálculos redundantes, levando a uma aceleração dramática, especialmente para problemas com subproblemas sobrepostos.
Veja como é utilizado:
1.
Identificando subproblemas sobrepostos: A programação dinâmica resolve problemas, dividindo -os em subproblemas menores e sobrepostos. Se o mesmo subproblema for encontrado várias vezes, a memórias poderá impedir o recálculo.
2.
armazenando resultados: Uma estrutura de dados, geralmente uma tabela de hash (dicionário em python) ou uma matriz, é usada para armazenar os resultados dos subproblemas. A entrada para o subproblema (por exemplo, os parâmetros de uma função recursiva) serve como chave, e o resultado calculado é o valor.
3.
verificando resultados em cache: Antes de calcular a solução para um subproblema, o algoritmo verifica o armazenamento para ver se o resultado já está disponível. Se for, o resultado em cache será retornado imediatamente.
4.
armazenar e retornar resultados: Se o resultado não for armazenado em cache, o algoritmo o calcula, o armazena na estrutura de dados e o retornará.
Exemplo (sequência de Fibonacci): Uma solução recursiva ingênua para a sequência de Fibonacci é altamente ineficiente devido a cálculos repetidos. A memomitação melhora drasticamente o seguinte:
Solução recursiva ingênua (ineficiente): `` `Python
def fibonacci_naive (n):
Se n <=1:
retornar n
retornar fibonacci_naive (n-1) + fibonacci_naive (n-2)
`` `
Solução recursiva memorada: `` `Python
Memorando ={} # Dicionário para memórias
def fibonacci_memo (n):
Se n em memorando:
Retornar memorando [n]
Se n <=1:
resultado =n
outro:
resultado =fibonacci_memo (n-1) + fibonacci_memo (n-2)
memorando [n] =resultado
resultado de retorno
`` `
Na versão memorizada:
* `Memo` armazena números de fibonacci previamente calculados.
* Antes de fazer uma chamada recursiva, `fibonacci_memo` verifica se o resultado para` n` já está em `memorando.
* Se for, o valor armazenado é retornado diretamente. Caso contrário, o resultado é calculado, armazenado em `memorando 'e depois retornado.
Essa mudança transforma um algoritmo de tempo exponencial em um algoritmo de tempo linear. A chave é evitar os cálculos redundantes dos mesmos números de Fibonacci várias vezes.
em essência: A memandoização transforma uma abordagem de programação dinâmica de cima para baixo (recursiva) em uma mais eficiente, cache os resultados intermediários. Ele complementa abordagens de tabulação (de baixo para cima), que também evitam cálculos redundantes, mas usam métodos iterativos em vez de recursão. A escolha entre memórias e tabulação geralmente depende do problema específico e da preferência do programador; Ambos atingem o mesmo objetivo de evitar cálculos redundantes.
