Algoritmi JavaScript: Risolvi la sequenza di Fibonacci (LeetCode)

I numeri di Fibonacci , comunemente indicati F(n)formano una sequenza, detta sequenza di Fibonacci , tale che ogni numero è la somma dei due precedenti, a partire da 0e 1. I numeri nella seguente sequenza di interi 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ……..

Questo è

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

Esempio 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

Esistono diverse opzioni per risolvere questo problema: Approccio ricorsivo.

Approccio ricorsivo

Un metodo semplice che è un'implementazione ricorsiva diretta di una relazione di ricorrenza matematica. Il modo più lento per risolvere questo problema perché richiede una complessità temporale esponenziale : O(2^N) e una complessità spaziale : O(N) .

Programmazione dinamica utilizzando la memoizzazione (approccio dall'alto verso il basso)

Possiamo evitare il lavoro ripetuto svolto in modo ricorsivo memorizzando i numeri di Fibonacci calcolati finora. Abbiamo solo bisogno di memorizzare tutti i valori in una mappa. Complessità temporale : O(N) e complessità spaziale : O(N) .

Approccio di iterazione

Iterazione, con risoluzione di tutti i sottoproblemi e restituzione della risposta per N elementi, utilizzando valori di Fibonacci già calcolati. Complessità temporale : O(N) e complessità spaziale : O(N) .

Approccio di iterazione ( spazio ottimizzato)

Possiamo ottimizzare l'approccio di iterazione memorizzando i due numeri precedenti solo perché è tutto ciò di cui abbiamo bisogno per ottenere il prossimo numero di Fibonacci in serie. Complessità temporale : O(N) e complessità spaziale : O(1) .

Approccio all'esponente di matrice

Usa Matrix Exponentiation per ottenere il numero di Fibonacci dall'elemento in (0, 0) nella matrice risultante. Per fare ciò possiamo fare affidamento sull'equazione della matrice per la sequenza di Fibonacci, per trovare l' N-esimo numero di Fibonacci:

Come funziona questa formula puoi guardare Wiki

Questa soluzione ha: complessità temporale : O(logN) e complessità spaziale : O(logN) .

Approccio matematico

Possiamo usare il golden ratio forumula:

Ecco un link per saperne di più su come funzionano la sequenza di Fibonacci e il rapporto aureo.

Questa soluzione ha: complessità temporale : O(logN) e complessità spaziale : O(1) .

Inoltre, a volte è necessario restituire non un valore per un dato N, ma restituire un array di elementi Fibonacci fino a un dato N.

Esempio:

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

e la programmazione dinamica utilizzando la memoizzazione con piccole modifiche:

Abbiamo considerato diverse opzioni per risolvere il problema di Fibonacci, la più difficile da capire è Matrix Exponentiation, ma di solito la conoscenza dei 4 metodi precedenti è sufficiente per un colloquio.

Spero ti sia stato utile!

Grazie per aver letto! A presto.

Altri contenuti su PlainEnglish.io . Iscriviti alla nostra newsletter settimanale gratuita . Seguici su Twitter , LinkedIn , YouTube e Discord . Interessato al Growth Hacking? Scopri Circuito .