Implementando Fibonacci: De O(2^N) a O(1)

No último artigo, 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