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?
Muito legal. Vou indicar para os alunos das disciplinas que eu dou aulas. Parabéns
A versão AWK dessa função seria assim
function F(n) {
if (!m[n]) m[n] = (n > 1)? F(n-1) + F(n-2) : n
return m[n]
}
$ time awk -v n=45 -f script.awk
fatorial de n = 45 : 1134903170
real 0m0.002s
user 0m0.000s
sys 0m0.000s
Detalhe que para a versão duplamente recursiva o awk, para calcular F(36), levou quase 22 segundos e para 45 ele ficou 3 minutos processando sem informar a resposta.
Ops, escrevi errado, é fibonacci e não fatorial, :$
@Elton Minetto, Valeu minetto!
@Thiago, Legal sua implementação em awk. Pelos resultados podemos ver também que C++ tem performasse muito maior que em awk(usando recursividade simples).
foi cerca de 60 vezes mais rápido.
Mas usando a técnica de programação dinâmica o tempo é o mesmo(0.002 para 0.007 podemos dizer que é desconsiderável).
Bacana! Um amigo meu fez uns testes em Python, acho que é legal vc dar uma olhada
http://montegasppa.blogspot.com/2006/07/desempenho-de-algoritmos.html
Felipe,
Comparando com a forma tradicional, por exemplo, eu gasto 2189 iterações para achar fib(20), 39 iterações usando programação dinamica e apenas 22 usando tail-recursion.
function G(N) { total++; return G_tr(N,0,1); }
function G_tr(I,R,N){
total++;
return (I==0)? R : G_tr(I-1,N,R+N)
}
onde total acumula as chamadas as funções.
Eu me inspirei na versão Erlang do algoritmo
http://en.literateprograms.org/Fibonacci_numbers_(Erlang)
Fibonacci me lembra a faculdade de engenharia.
Boas lembranças, acho!
E bacana teu blog!
[]s!
olá,
iniciei ontem aulas de algoritmo (sou biologa, imagine o desespero). Tenho uma atividade para escrever um algoritmo que expresse a razão de uma sequencia for o numero da termo da sequencia de fibonacci essa sequencia tem q ser proximal a 10…
Não entendi nada que
Por favor ajude
Att,
Erica
Bem legal o seu blog.
Parabéns.