Algoritmos de JavaScript: resuelve la secuencia de Fibonacci (LeetCode)

Los números de Fibonacci , comúnmente denotados, F(n)forman una secuencia, llamada secuencia de Fibonacci , tal que cada número es la suma de los dos anteriores, comenzando por 0y 1. Los números en la siguiente secuencia de enteros 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ……..

Es decir

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

Ejemplo 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

Hay varias opciones para resolver este problema: Enfoque de recursividad.

Enfoque recursivo

Un método simple que es una relación de recurrencia matemática de implementación recursiva directa. La forma más lenta de resolver este problema porque requiere complejidad de tiempo exponencial : O(2^N) y complejidad de espacio : O(N) .

Programación dinámica utilizando memorización (enfoque de arriba hacia abajo)

Podemos evitar el trabajo repetido realizado en recursivo almacenando los números de Fibonacci calculados hasta ahora. Solo necesitamos almacenar todos los valores en un mapa. Complejidad temporal : O(N) y complejidad espacial : O(N) .

Enfoque de iteración

Iteración, con la resolución de todos los subproblemas y la devolución de la respuesta para el elemento N, utilizando valores de Fibonacci ya calculados. Complejidad temporal : O(N) y complejidad espacial : O(N) .

Enfoque de iteración ( espacio optimizado)

Podemos optimizar el enfoque de iteración almacenando los dos números anteriores solo porque eso es todo lo que necesitamos para obtener el siguiente número de Fibonacci en serie. Complejidad temporal : O(N) y complejidad espacial : O(1) .

Enfoque de exponenciación matricial

Use la exponenciación de matrices para obtener el número de Fibonacci del elemento en (0, 0) en la matriz resultante. Para hacer esto, podemos basarnos en la ecuación matricial de la secuencia de Fibonacci, para encontrar el N-ésimo número de Fibonacci:

¿Cómo funciona esta fórmula? Puedes mirar Wiki

Esta solución tiene: complejidad de tiempo : O(logN) y complejidad de espacio : O(logN) .

Enfoque matemático

Podemos usar el golden ratio forumula:

Aquí hay un enlace para obtener más información sobre cómo funcionan la secuencia de Fibonacci y la proporción áurea.

Esta solución tiene: complejidad de tiempo : O(logN) y complejidad de espacio : O(1) .

Además, a veces se requiere devolver no un valor para un N dado, sino una matriz de elementos de Fibonacci hasta un N dado.

Ejemplo:

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

y Programación Dinámica usando memorización con pequeños cambios:

Hemos considerado diferentes opciones para resolver el problema de Fibonacci, la más difícil de entender es la Exponenciación de Matrices, pero por lo general el conocimiento de los 4 métodos anteriores es suficiente para una entrevista.

¡Espero que te haya sido útil!

¡Gracias por leer! Te veo pronto.

Más contenido en PlainEnglish.io . Regístrese para recibir nuestro boletín semanal gratuito . Síganos en Twitter , LinkedIn , YouTube y Discord . ¿Interesado en el Growth Hacking? Visita Circuito .