Algorithmes JavaScript : résoudre la séquence de Fibonacci (LeetCode)

Les nombres de Fibonacci , communément notés F(n)forment une suite, appelée suite de Fibonacci , telle que chaque nombre est la somme des deux précédents, à partir de 0et 1. Les nombres dans la séquence entière suivante 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ……..

C'est

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

Exemple 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

Il existe plusieurs options pour résoudre ce problème : Approche récursive.

Approche récursive

Une méthode simple qui est une relation de récurrence mathématique à implémentation récursive directe. La manière la plus lente de résoudre ce problème car elle prend une complexité temporelle exponentielle : O(2^N) et une complexité spatiale : O(N) .

Programmation dynamique utilisant la mémorisation (approche descendante)

On peut éviter le travail répété effectué en récursif en stockant les nombres de Fibonacci calculés jusqu'à présent. Nous avons juste besoin de stocker toutes les valeurs dans une carte. Complexité temporelle : O(N) et complexité spatiale : O(N) .

Approche d'itération

Itération, avec résolution de tous les sous-problèmes et retour de la réponse pour N élément, en utilisant des valeurs de Fibonacci déjà calculées. Complexité temporelle : O(N) et complexité spatiale : O(N) .

Approche d'itération ( espace optimisé)

Nous pouvons optimiser l'approche d'itération en stockant les deux nombres précédents uniquement parce que c'est tout ce dont nous avons besoin pour obtenir le prochain nombre de Fibonacci en série. Complexité temporelle : O(N) et complexité spatiale : O(1) .

Approche d'exponentiation matricielle

Utilisez Matrix Exponentiation pour obtenir le nombre de Fibonacci à partir de l'élément à (0, 0) dans la matrice résultante. Pour ce faire, nous pouvons nous appuyer sur l'équation matricielle de la suite de Fibonacci, pour trouver le N-ème nombre de Fibonacci :

Comment fonctionne cette formule, vous pouvez regarder Wiki

Cette solution a : complexité temporelle : O(logN) et complexité spatiale : O(logN) .

Approche mathématique

Nous pouvons utiliser le golden ratio forumula:

Voici un lien pour en savoir plus sur le fonctionnement de la suite de Fibonacci et du nombre d'or.

Cette solution a : complexité temporelle : O(logN) et complexité spatiale : O(1) .

De plus, il est parfois nécessaire de ne pas renvoyer une valeur pour un N donné, mais de renvoyer un tableau d'éléments de Fibonacci jusqu'à un N donné.

Exemple:

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

et Programmation dynamique utilisant la mémorisation avec peu de changements :

Nous avons envisagé différentes options pour résoudre le problème de Fibonacci, la plus difficile à comprendre est l'exponentiation matricielle, mais généralement la connaissance des 4 méthodes précédentes est suffisante pour un entretien.

J'espère que cela vous a été utile !

Merci d'avoir lu! À bientôt.

Plus de contenu sur PlainEnglish.io . Inscrivez-vous à notre newsletter hebdomadaire gratuite . Suivez-nous sur Twitter , LinkedIn , YouTube et Discord . Intéressé par le Growth Hacking ? Découvrez Circuit .