O número de Fibonacci é bem conhecido no mundo da computação. Ele é representado por uma função recursiva:

Calculando

Tendo isso em mente é bem fácil criar um algoritmo que calcule o número de Fibonacci, certo?
Na internet normalmente encontramos um algoritmo usando um método de recursão simples. Algo parecido com:

Felipe: Esse artigo usa apenas exemplos em C++

fibo1.cpp

#include <iostream>
#include <cstdlib>
 
int F(int n)
{
    if (n == 0) return 0;
    if (n == 1) return 1;
    return F(n - 1) + F(n - 2);
}
 
int main(int argc, char *argv[])
{
    int n = atoi(argv[1]);
    std::cout << F(n) << std::endl;
    return 0;
}

código no pastebin

Compilando:

g++ -o fibo1 fibo1.cpp

Rodando:

./fibo1 8

Deu 21, certo? Isso mesmo.

Analisando a Função

Mas digo para você: Não use esse programa! É totalmente ineficiente. O número de chamadas para calcular é exatamente . A função calcula recursivamente o mesmo número quantas vezes a chamar. Como podemos ver, a taxa de crescimento do número de Fibonacci tende a Proporção áurea:

Lembrando que a razão áurea é definida por:

Sim, fibo1.cpp é uma função exponencial com Big Theta Notation, em função do tempo, de:

O tempo de execução para computar é vezes mais demorado que para calcular . Por exemplo, já que e percebemos que nosso computador leva um segundo para calcular , então levará mais de um minuto para calcular e mais de uma hora para calcular .

Podemos verificar isso calculando e

pet@felipe-opensuse:~/Projetos/C++/algoritmos> time ./fibo1 36
14930352

real 0m1.077s
user 0m1.040s
sys 0m0.008s
pet@felipe-opensuse:~/Projetos/C++/algoritmos> time ./fibo1 45
1134903170

real 0m54.927s
user 0m54.547s
sys 0m0.092s

Em contraste, usando o método de programação dinâmica temos um tempo proporcional a N.

Programação dinâmica

Esse método consiste em guardar os valores dos números já calculados em um array. Fazendo isso, apenas checamos se o array já foi memorizado, e então retornamos o número, caso contrário calculamos recursivamente e assim por diante.
Lembrando que para um int de 32 bits, será o maior numero a ser calculado.

fibo2.cpp

#include <iostream>
#include <cstdlib>
 
namespace Fibonacci {
    int *memory;
    int F(int n)
    {
        // int inicializa como 0
        if (memory[n] != 0) return memory[n];
        int aux = n;
        if (n < 0) return 0;
        if (n > 1) aux = F(n-1) + F(n-2);
        return memory[n] = aux;
    }
}
 
int main(int argc, char *argv[])
{
    int n = atoi(argv[1]);
    Fibonacci::memory = new int[n+1];
    std::cout << Fibonacci::F(n) << std::endl;
    delete [] Fibonacci::memory;
    return 0;
}

código no pastebin

Compilando:

g++ -o fibo2 fibo2.cpp

Rodando:

./fibo2 8

Deu 21, de novo? =)

Aplicamos aqui uma técnica chamada bottom-up dynamic programming. Se aplica em uma função recursiva que podemos salvar tempo por armazenar valores anteriores que serão usados depois. Essa técnica tem sido usada para uma gama grande de algoritmos e aplicações. E essa simples mudança fez com que nosso algoritmo passasse de exponencial para linear.

Agora temos uma função, em relação ao tempo, proporcional ao N.

Comparando

Fazendo vários testes, podemos chegar em uma tabela de resultados, em função do tempo:

arquivo
fibo1.cpp	0m0.009s	0m1.156s	0m54.927s	1m29.403s
fibo2.cpp	0m0.007s	0m0.007s	0m0.006s	0m0.007s

fibo2.cpp é constante? Sim! Para N relativamente pequeno fibo2.cpp calcula em tempo constante.

Será interessante ver até quanto esse algoritmo agüenta(ta errado né? hehe ¬¬) fazer em tempo constante. Alguém se habilita?