DEV Community: José

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

José — Sat, 16 Nov 2024 17:27:33 +0000

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

Fibonacci, Integer overflow, memoization e um exagero

José — Fri, 11 Oct 2024 21:36:56 +0000

Vamos fazer um exercício.
Abaixo deixo um código que retorna o número na posição n da sequência de Fibonacci:

public static int fib(int n){
   if (n <= 1){
     return n;
   }
   return fib(n-1) + fib(n-2);
}

Que tal tentarmos mostrar no nosso terminal todos os números da sequência de fibonacci menores que 2147483647?

    public static int fib(int n){
       if (n <= 1){
           return n;
       }
       return fib(n-1) + fib(n-2);
    }

    public static void main(String[] args) {
        int position = 1;
        int currentNumber = fib(position);

        while (currentNumber < 2147483647) {
            System.out.println(currentNumber);
            position++;
            currentNumber = fib(position);
        }
    }

Os problemas

Ao executar o código, você vai perceber dois problemas principais:

Nosso loop nunca termina, e, estranhamente, números negativos passam a aparecer no console.
O código fica cada vez mais lento conforme o tempo passa.

Problema 1: Os números negativos

Ignora por um momento toda essa história de fibonacci e olhe esse código.

public static void main(String[] args) {
   int a = 2_000_000_000;
   int b = 2_000_000_000;
   System.out.println(a + b);
}

Quanto você acha que vai ser o resultado disso? 2 bilhões + 2 bilhões = 4 bilhões certo? Então no nosso código o resultado vai ser 4 bilhões... certo?

ERRADO!

A saída na verdade foi essa:

O motivo para esse resultado é o overflow. O tipo int tem um limite máximo de 2147483647 (ou 2^31 - 1). Quando esse limite é ultrapassado, o valor "retorna" ao menor valor possível do tipo int, que é -2147483648.

Por que nosso loop não parou?

Nosso loop deveria parar quando chegássemos a um número maior ou igual a 2147483647, mas como os valores de Fibonacci ultrapassaram o limite de int, números negativos começaram a ser gerados. Como nunca chegamos a um número maior que 2147483647, o loop nunca parou.

Solução para o problema 1

Pra manter as coisas simples, eu apenas mudarei o tipo de retorno da nossa função fib de int pra long que tem um limite muito maior. Nosso código ficará assim:

    public static long fib(long n){
       if (n <= 1){
           return n;
       }
       return fib(n-1) + fib(n-2);
    }

    public static void main(String[] args) {
        long position = 1;
        long currentNumber = fib(position);

        while (currentNumber < Integer.MAX_VALUE) {
            System.out.println(currentNumber);
            position++;
            currentNumber = fib(position);
        }
    }

Agora, com o tipo long, conseguimos imprimir corretamente os números do Fibonacci até o maior número menor que 2147483647.

Resolvendo o problema 2: lentidão

Já percebeu uma coisa? Toda iteração do nosso loop a função fib recalcula todos os números anteriores da sequência. Ou seja, estamos repetindo cálculos desnecessários.

Como evitar recálculos desnecessários? Apresento-lhes: Memoization. A técnica de memoization é uma forma de guardar resultados já calculados para não passar novamente pelo processo de cálculo.

Vamos implementar um HashMap para guardar os valores já encontrados, onde a chave será a posição e o valor é o próprio número.


    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;
    }

    public static void main(String[] args) {
        long position = 1;
        long currentNumber = fib(position);

        while (currentNumber < 2147483647) {
            System.out.println(currentNumber);
            position++;
            currentNumber = fib(position);
        }
    }

Lindo! Agora nosso código roda muuito mais rápido e resolvemos nosso problema.

O exagero

Na verdade, memoization não era necessário aqui. Eu só quis trazer para ensinar esse conceito. Nós podíamos simplesmente calcular cada número do Fibonacci até acabarmos nossa condição dessa forma:

    public static void main(String[] args) {
        long prev1 = 0;
        long prev2 = 1;
        long current;

        System.out.println(prev1);

        while (prev2 < 2147483647) {
            System.out.println(prev2);
            current = prev1 + prev2;
            prev1 = prev2;
            prev2 = current;
        }
    }

Acabei com a graça né? Desculpa! Mas espero que tenha aprendido algo novo.

Capa do artigo por: Gerd Altmann do Pixabay