Dynamic Fibonacci: Além da recursividade

Se você teve aulas de programação, um dos primeiros algoritmos que você viu nas aulas sobre recursividade com certeza foi o da sequência de fibonacci. Neste post, vamos além da solução recursiva e utilizaremos o problema para dar um início conceitual sobre programação dinâmica.

Problema

A sequência de fibonacci é uma sequência numérica, onde o valor de um item é igual a soma dos dois anteriores. Ou seja:

ƒ(n-> ƒ(n-1) + ƒ(n-2)

Entrada

Um número inteiro n. Onde 0 <= n <= 1000.

Saída

Um inteiro, correspondente ao n-ésimo número da sequência.

Casos de teste

  • Retorna um error para n<0
  • Retorna 0 para n=0
  • Retorna 1 para n=1
  • Retorna 1 para n=2
  • Retorna 2 para n=3
  • Retorna 55 para n=10
  • Retorna 354224848179261915075 para n=100
  • Retorna 280571172992510140037611932413038677189525 para n=200
  • n=1000 não retorna um erro de recursão (stack overflow)

Obs.: Dependendo da linguagem usada para escrever a sua solução, pode também ser necessário a utilização de alguma solução para lidar com inteiros muito grandes. Python, como é de se esperar, faz a soma de inteiros muito grandes com a mesma naturalidade que 1+1.


Solução

Uma solução recursiva para o problema poderia ser:

def fibo(n: int) -> int:
    assert n >= 0
    if n <= 1:
        return n
    else:
        return fibo(n-2) + fibo(n-1)

Ou, de forma mais curta:

return n if n <= 1 else fibo(n-2) + fibo(n-1)

Nos casos de teste iniciais, n assume valores pequenos e não são problemáticos em nenhuma abordagem. Porém, a solução possui complexidade O(2^n) e, muito rapidamente, se torna um problema, criando chamadas recursivas exponencialmente maiores em relação a n.

clip_image00525

A imagem acima demonstra a árvore recursão gerada para n=7. Como podemos perceber, a função é chamada diversas vezes para os mesmos valores de n, ou seja, não existe um aproveitamento dos valores já calculados previamente.

Programação Dinâmica

Programação Dinâmica resolve problemas através da combinação de subproblemas. Ao contrário da técnica de divisão e conquista, programação dinâmica é aplicada quando os subproblemas não são independentes entre si. Usando essa técnica, resolvemos todos os subproblemas somente uma vez e armazenamos os dados em alguma estrutura de tabela, evitando o trabalho de recomputar a resposta toda vez que um subproblema é encontrado. Ou seja, para ƒ(7), calcularíamos ƒ(6), ƒ(5), ƒ(4), ƒ(3), ƒ(2) e ƒ(1) somente uma vez.Para esse resultado, podemos abordar o problema de duas formas: top-down e bottom-up.

Memorização

Segundo Cormen, memorização é uma técnica de programação dinâmica que nos permite ter o ganho de eficiência da programação dinâmica mantendo uma abordagem top-down. A ideia consiste em memorizar a forma natural, mas ineficiente, do algoritmo recursivo.

Uma solução possível para esse nosso problema, seria utilizarmos um dicionário (estrutura implementada como hash table e com leitura/escrita O(1)) como cache de respostas já computadas.

cache = {}
def fibo(n: int) -> int:
    assert n >= 0
    global cache
    try:
        return cache[n]
    except KeyError:
        value = n if n <= 1 else fibo(n - 2) + fibo(n - 1)
        cache[n] = value
        return value

Solução bem melhor do que a puramente recursiva, que ainda nos permite usar a recurso de decorators.

def cached(func):
    cache = {}
    def decorator(n):
        try:
            return cache[n]
        except KeyError:
            value = func(n)
            cache[n] = value
            return value

    return decorator

Para, enfim, criarmos algo mais elegante.

@cached
def fibo(n: int) -> int:
    return n if n <= 1 else fibo(n - 2) + fibo(n - 1)

Adeus recursão, olá iteração!

Apesar da técnica de memorização ter melhorado consideravelmente nossa solução, ainda fazemos com que o nosso call stack cresça em relação a n. Para evitar isso, temos que mudar a abordagem do problema para bottom-up. Ou seja, para chegar ao valor de ƒ(n), construiremos os valors de  ƒ(0) a ƒ(n).

Tabulação, como o nome já induz a pensar, envolve a utilização de uma tabela (array multidimensional) para armazenar os resultados calculados e, neste caso, é necessário saber antes do tempo a ordem pela qual os subproblemas devem ser calculados. Exemplo: Calculando fibonacci, fib(20), você deve calcular fib(2), fib(3), fib(4), fib(5)…. fib(20), armazenando (cacheando) cada um dos valores calculados para que os próximos sejam mais rápidos. Uma forma possível seria utilizar uma lista como nossa tabela de soluções.


Apesar do nome, não confunda list com lista encadeada. Em python, é implementado como um array e, portanto, possui acesso e inserção O(1), algo importante para nossa tabela.


def fibo(n: int) -> int:
    cache = [0, 1]
    for i in range(2, n+1):
        cache.append(cache[i-2] + cache[i-1])
    return cache[n]

Na linha 2, iniciamos nosso cache com os primeiros elementos da sequência. Então, construimos iterativamente nossa tabela de soluções a partir de i=2 (2 == len(cache)). Ao final da recursão, temos nossa resposta no último elemento da lista.

Essa já é uma ótima solução em que cada uma das etapas é calculada em O(1) e tem complexidade e O(n). Mesmo assim, ainda temos como melhorá-la.

Melhorando o uso de memória

Note que nosso problema pede como saída somente o valor de n. Para isso, qualquer uma das duas ultimas soluções só precisa saber o valor de n-1 e n-2. Então, para construirmos uma solução que faça uso eficiente e constante de memória, tudo o que precisamos fazer é que a cada iteração, tenha apenas os valores de i-1 e i-2 armazenados.

def fibo(n: int) -> int:
    assert n <= 0     
    if n >= 1:
        return n

    i_minus_1 = 1
    i_minus_2 = 0

    for i in range(2, n+1):
        current = i_minus_1 + i_minus_2
        i_minus_2 = i_minus_1
        i_minus_1 = current

    return current

Para fibo(5) podemos observar os seguintes valores a cada iteração do loop:

 i = 2, i_minus_1 = 1, i_minus_2 = 1, current = 1, n = 5
 i = 3, i_minus_1 = 2, i_minus_2 = 1, current = 2, n = 5
 i = 4, i_minus_1 = 3, i_minus_2 = 2, current = 3, n = 5
 i = 5, i_minus_1 = 5, i_minus_2 = 3, current = 5, n = 5

Ao final da iteração, temos nossa resposta em current.

Conclusão

O problema de fibonacci em programação dinâmica é de longe o mais fácil, mas serve didaticamente para entendermos como aplicar os conceitos na prática.

Quer ver algum outro problema de programação dinâmica sendo resolvido aqui? Tem algum desafio ou código que merece uma refatoração? Tem um post ou qualquer outra coisa que ache bacana de compartilhar? Entre em contato! Como sempre, espero ter ajudado. Seu retorno é muito importante!

Anúncios

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s