No último artigo (Fibonacci, Integer overflow, memoization e um exagero), eu mostrei um código Fibonacci que era bem lento. Fui otimizando ele usando memoization e também mostrando uma outra implementação com loops. Agora vou detalhar mais e mostrar algumas soluções alternativas que aprendi nesse meio tempo.
Pra facilitar, usarei a notação Big O pra explicar como é a performance de cada implementação.
1. O(2^N) O clássico, mas lento.
public static long fib(long n){
if(n <= 1){
return n;
}
return fib(n-2) + fib(n-1);
}Essa é uma implementação comum. Funciona? Claro! Mas se liga como fica a nossa pilha de chamadas caso quisermos o número na posição 5 da sequência:
Percebe que cada chamada gera mais duas? E pior, algumas delas, como fib(3)e fib(2) são repetidas várias vezes, recalculando tudo de novo.
No total, são 11 passos pra encontrar o número na posição 5 da sequência de Fibonacci, há um crescimento exponencial: cada chamada da função inicia mais uma ou duas chamadas. Assim, a complexidade do algoritmo tem como pior caso O(2^N).
Se quisermos ser precisos, na verdade, o crescimento segue a proporção áurea (≈1,618), sendo então O(1,618^N).
Agora imagina o impacto:
- Se N = 10 → 122 passos.
- N = 30 → MAIS DE 1 MILHÃO DE PASSOS!!
Com memoization podemos evitar cálculos repetidos. Assim, o algoritmo se torna O(N) em tempo, mas com um custo de memória adicional (pelo cache).
static HashMap<Long, Long> memo = new HashMap<>();
public static long fib(long n) {
if (memo.containsKey(n)) {
return memo.get(n);
}
if (n <= 1) {
return n;
}
long result = fib(n - 1) + fib(n - 2);
memo.put(n, result);
return result;
}Mas dá pra gente resolver o mesmo problema sem consumir mais memória.
2. O(N) Tail recursion
Podemos adicionar dois novos parâmetros à função (os dois últimos números da sequência atual). Assim, não há recálculo e a complexidade continua O(N), mas sem custo extra de memória:
public static long fib(long a, long b, long n){
if (n <= 2){
return b;
}
return fib(b,a+b, n-1);
}Aqui a pilha de chamadas para N = 5
Sem memoization, sem crescimento exponencial… perfecto! Percebe como as recursões mudaram bastante? A primeira era uma recursão binária (cada chamada gerava mais duas, um crescimento exponencial), enquanto essa é uma tail recursion: a chamada recursiva ocorre como a última operação da função, de modo que o resultado da função não depende mais de cálculos adicionais após a chamada recursiva.
3. O(N) com Dynamic Programming
Sem recursão, mas com o mesmo raciocínio da solução anterior. Nada de cálculos desnecessários, criamos 2 variavéis para os 2 últimos valores calculados e seguimos com a sequência.
long fib(long n){
long a = 1;
long b = 1;
for(long current = 2; current < n; current++) {
long tmp = a;
a = b;
b = b + tmp;
}
return b;
}4. O(1) com a formula de Binet
Usando a fórmula de Binet, podemos calcular diretamente, mas isso só funciona enquanto n < 71, por culpa dos problemas de imprecisão nos cálculos com ponto flutuante.
Sem loops ou recursão, só copiando e colando uma fórmula.
public static long fib(long n) {
double A = Math.pow((1 + Math.sqrt(5)) / 2, n);
double B = Math.pow((1 - Math.sqrt(5)) / 2, n);
return (long) ((A - B) / Math.sqrt(5));
}Referências & Inspirações
https://craftofcoding.wordpress.com/2021/12/10/fibonacci-by-linear-recursion-is-better/ (thx @geckones)
https://artofproblemsolving.com/wiki/index.php/Binet%27s_Formula