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; }
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
14930352real 0m1.077s
user 0m1.040s
sys 0m0.008s
pet@felipe-opensuse:~/Projetos/C++/algoritmos> time ./fibo1 45
1134903170real 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; }
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?







Recent Comments