Algoritmos JavaScript: Resolva a Sequência de Fibonacci (LeetCode)

Os números de Fibonacci , comumente denotados F(n)formam uma sequência, chamada de sequência de Fibonacci , de modo que cada número é a soma dos dois anteriores, começando de 0e 1. Os números na seguinte sequência inteira 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ……..

Aquilo é

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.

Exemplo 1:

Input: n = 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.

Input: n = 3
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.

Input: n = 4
Output: 3
Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.

• 0 <= n <= 30

Existem várias opções para resolver este problema: Abordagem de Recursão.

Abordagem de Recursão

Um método simples que é uma relação de recorrência matemática de implementação recursiva direta. A maneira mais lenta de resolver este problema porque requer complexidade de tempo exponencial : O(2^N) e complexidade de espaço : O(N) .

Programação dinâmica usando memoização (abordagem de cima para baixo)

Podemos evitar o trabalho repetido feito em recursiva armazenando os números de Fibonacci calculados até agora. Só precisamos armazenar todos os valores em um mapa. Complexidade de tempo : O(N) e complexidade de espaço : O(N) .

Abordagem de iteração

Iteração, resolvendo todos os subproblemas e retornando a resposta para o elemento N, usando valores de Fibonacci já calculados. Complexidade de tempo : O(N) e complexidade de espaço : O(N) .

Abordagem de iteração ( espaço otimizado)

Podemos otimizar a abordagem de iteração armazenando os dois números anteriores apenas porque isso é tudo de que precisamos para obter o próximo número de Fibonacci em série. Complexidade de tempo : O(N) e complexidade de espaço : O(1) .

Abordagem de Exponenciação de Matrizes

Use a Exponenciação de matrizes para obter o número de Fibonacci do elemento em (0, 0) na matriz resultante. Para fazer isso, podemos contar com a equação da matriz para a sequência de Fibonacci, para encontrar o N-ésimo número de Fibonacci:

Como funciona esta fórmula, você pode ver Wiki

Esta solução tem: complexidade de tempo : O(logN) e complexidade de espaço : O(logN) .

Abordagem matemática

Podemos usar o golden ratio forumula:

Aqui está um link para saber mais sobre como a sequência de Fibonacci e a proporção áurea funcionam.

Esta solução tem: complexidade de tempo : O(logN) e complexidade de espaço : O(1) .

Além disso, às vezes é necessário retornar não um valor para um determinado N, mas retornar uma matriz de elementos de Fibonacci até um determinado N.

Exemplo:

Input: n = 7
Output: [0, 1, 1, 2, 3, 5, 8, 13]

e Programação Dinâmica usando memoização com pequenas alterações:

Consideramos diferentes opções para resolver o problema de Fibonacci, a mais difícil de entender é a Exponenciação de Matrizes, mas geralmente o conhecimento dos 4 métodos anteriores é suficiente para uma entrevista.

Espero que tenha sido útil para você!

Obrigado por ler! Vejo você em breve.

Mais conteúdo em PlainEnglish.io . Assine nosso boletim informativo semanal gratuito . Siga-nos no Twitter , LinkedIn , YouTube e Discord . Interessado em Growth Hacking? Conheça o Circuito .