Memoização

4.1 Definição de memoização e seus conceitos-chave

Memoização é uma técnica de otimização onde os resultados de funções custosas são armazenados, para que possam ser reutilizados em chamadas subsequentes com os mesmos argumentos. Isso reduz o número de recalculações, aumentando a performance.

Conceitos-chave:

1. Caching:

Armazenar os resultados de uma função em alguma estrutura de dados (como um dicionário ou lista) para que ao chamar novamente com os mesmos argumentos seja retornado o resultado já armazenado, sem recalcular.

2. Tabela de busca (Lookup Table):

Estrutura de dados usada para armazenar os resultados de chamadas anteriores de uma função. Pode ser uma hash table (dicionário) ou lista.

3. Chamadas recursivas:

Memoização é especialmente útil para funções recursivas, onde as mesmas sub-tarefas podem ser executadas várias vezes com os mesmos parâmetros.

Complexidade temporal e espacial de algoritmos otimizados:

Complexidade temporal:

Para muitas tarefas recursivas, a memoização reduz a complexidade temporal ao diminuir o número de recalculações. Por exemplo, o cálculo recursivo de números de Fibonacci tem complexidade temporal O(2^n), mas com memoização é O(n).

Complexidade espacial:

A complexidade espacial aumenta devido ao armazenamento dos resultados no cache. Geralmente é O(n) para uma tarefa que requer memoização.

Resumo:

Memoização é uma técnica poderosa para otimizar algoritmos recursivos, permitindo melhorar significativamente sua performance ao reduzir o número de recalculações.

É especialmente útil para tarefas onde as mesmas sub-tarefas são executadas repetidamente com os mesmos parâmetros. Compreender os conceitos de memoização e seu uso na prática permite resolver eficientemente tarefas de alto custo computacional.

4.2 Exemplos de otimização

Exemplos de otimização de algoritmos recursivos com memoização

Exemplo 1: Números de Fibonacci

O algoritmo recursivo para calcular números de Fibonacci sem memoização tem complexidade temporal exponencial. O uso de memoização melhora consideravelmente a performance.

def fibonacci(n, memo=None):
    if memo is None:
        memo = {}
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
    return memo[n]
        
# Exemplo de uso:
print(fibonacci(10))  # Saída: 55
        

Importante! Note que usamos memo=None como valor padrão, e então criamos um dicionário vazio dentro da função se memo não for passado. Isso evita o problema de usar um objeto mutável como valor padrão.

Exemplo 2: Soma de subconjuntos

É necessário determinar se existe um subconjunto de um conjunto dado cuja soma dos elementos é igual a um valor especificado.

def is_subset_sum(arr, n, sum_value, memo=None):
    if memo is None:
        memo = {}
    if (n, sum_value) in memo:
        return memo[(n, sum_value)]
    if sum_value == 0:
        return True
    if n == 0 and sum_value != 0:
        return False
    if arr[n - 1] > sum_value:
        memo[(n, sum_value)] = is_subset_sum(arr, n - 1, sum_value, memo)
        return memo[(n, sum_value)]
    memo[(n, sum_value)] = is_subset_sum(arr, n - 1, sum_value, memo) or is_subset_sum(arr, n - 1, sum_value - arr[n - 1], memo)
    return memo[(n, sum_value)]
        
# Exemplo de uso:
arr = [3, 34, 4, 12, 5, 2]
sum_value = 9
n = len(arr)
print(is_subset_sum(arr, n, sum_value))  # Saída: True
        

Memoização é, de fato, o armazenamento em cache dos resultados de sub-tarefas.

Por exemplo, o número de Fibonacci F(10) == F(9) + F(8), mas para calcular F(9), é necessário calcular F(8) e F(7). Ou seja, F(8) deve ser calculado duas vezes: como o primeiro termo para F(9) e como o segundo termo para F(10). Para não calculá-lo duas vezes, precisamos armazená-lo em cache após o primeiro cálculo.

1

Pesquisa/teste

Recursão, nível 57, lição 3

Indisponível

Recursão

Recursão

Abrir