Fibonacci Number

Q: Qual è la complessità temporale della funzione ricorsiva di Fibonacci?

La ricorsione ingenua effettua 2 × F(n+1) - 1 chiamate, un numero che cresce come 1.618^n e che di solito si scrive O(2^n) . Per n = 45 sono circa 3.7 × 10^9 chiamate. Memorizzando ogni risultato una sola volta, in una tabella o in due variabili, si riduce a O(n) .

Q: Come si risolve Fibonacci con la programmazione dinamica?

Parti dalla ricorrenza F(n) = F(n-1) + F(n-2) e calcola i valori in ordine crescente di n , memorizzandoli uno per uno. Puoi riempire una tabella dal basso verso l’alto oppure mantenere la funzione ricorsiva e memorizzarne nella cache i risultati: questo si chiama memoizzazione. In entrambi i casi ogni valore viene calcolato una sola volta, quindi il lavoro totale è O(n) .

Q: È possibile calcolare Fibonacci con spazio O(1)?

Sì. Ogni numero dipende solo dai due precedenti, quindi bastano due variabili. Conserva gli ultimi due valori e falli avanzare a ogni passaggio. Questo richiede un tempo O(n) e uno spazio aggiuntivo O(1) .

Q: C'è un modo più veloce di O(n)?

Sì. La matrice [[1, 1], [1, 0]] elevata alla potenza n contiene F(n) nell'angolo in alto a destra, e l'elevamento al quadrato ripetuto calcola quella potenza con O(log n) moltiplicazioni di matrici. Esiste anche una formula chiusa con le potenze del rapporto aureo, ma usa l'aritmetica in virgola mobile e perde precisione man mano che n cresce, quindi sono preferibili i metodi con numeri interi.

PrincipianteProgrammazione dinamica Ricorsione

+10

I numeri di Fibonacci iniziano con F(0) = 0 e F(1) = 1, e ogni numero successivo è la somma dei due precedenti: F(n) = F(n-1) + F(n-2). La sequenza inizia con 0, 1, 1, 2, 3, 5, 8, 13. La tua funzione riceve n e restituisce F(n).

Funzione

fib(n: integer) → integer

ninteger: la posizione nella sequenza di Fibonacci, contando da 0
Restituisceinteger: il numero di Fibonacci F(n)

Vincoli

0 ≤ n ≤ 45
La risposta rientra in un intero con segno a 32 bit: F(45) = 1134903170.

Esempi

Input: n = 4
Output: 3
Spiegazione: Conta a partire dall'inizio: F(2) = 1 + 0 = 1, F(3) = 1 + 1 = 2 e F(4) = 2 + 1 = 3.

Input: n = 10
Output: 55
Spiegazione: La sequenza a partire dall'indice 0 è 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55. Il numero all'indice 10 è 34 + 21 = 55.

+13 test nascosti all’invio

Per approfondire

Riesci a calcolare F(n) in O(log n) tempo?

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

La definizione è già una funzione ricorsiva e scriverla come tale dà la risposta giusta. La trappola è il tempo di esecuzione: le due chiamate ricorsive ripetono il lavoro l'una dell'altra e il numero di chiamate cresce esponenzialmente con n. La programmazione dinamica risolve il problema calcolando ogni numero di Fibonacci una sola volta, dal basso verso l'alto. L'ultimo passaggio conserva solo i due numeri necessari per calcolare quello successivo.

Ricorsione direttamente dalla definizione

Corretto, ma non termina sui test più grandi

Intuizione

Traduci la definizione parola per parola. fib(0) è 0, fib(1) è 1 e qualsiasi valore più grande restituisce fib(n-1) + fib(n-2). Ogni catena di chiamate termina in uno dei due casi base, quindi la risposta è corretta.

Ora conta le chiamate. fib(5) chiama fib(4) e fib(3), ma fib(4) chiama di nuovo fib(3). Alla fine fib(3) viene eseguita due volte, fib(2) tre volte e fib(1) cinque volte, e fib(5) effettua 15 chiamate in totale. Gli stessi valori vengono ricalcolati più e più volte.

Il numero di chiamate segue i numeri di Fibonacci stessi: calcolare F(n) comporta 2 × F(n+1) - 1 chiamate. Per n = 45 sono circa 3.7 × 10^9 chiamate, troppe per un limite di tempo. Il limite superiore viene solitamente indicato come O(2^n); la crescita esatta è circa 1.618^n. La ricorsione è profonda solo n livelli, quindi lo stack richiede O(n) spazio.

Algoritmo

Se n è 0 o 1, restituisci n.
Altrimenti, chiama la funzione su n-1 e su n-2.
Restituisci la somma dei due risultati.

def fib(n):
    if n < 2:
        return n  # F(0) = 0, F(1) = 1
    return fib(n - 1) + fib(n - 2)

Compila una tabella dal basso verso l’alto

Intuizione

La ricorsione è lenta solo perché dimentica. Se annoti ogni numero di Fibonacci la prima volta che lo calcoli, ciascuno richiede una sola addizione. Crea una tabella f con slot per gli indici da 0 a n, imposta f[0] = 0 e f[1] = 1 e riempi il resto da sinistra a destra con f[i] = f[i-1] + f[i-2].

L’ordine da sinistra a destra è ciò che la fa funzionare: quando arrivi a f[i], entrambi i numeri di cui ha bisogno sono già nella tabella. Per n = 10 la tabella si riempie con 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 e la risposta è l’ultimo slot.

Questa è la programmazione dinamica nella sua forma più semplice: una relazione di ricorrenza più una tabella di risposte a casi più piccoli. Ci sono n-1 addizioni, tempo O(n) e la tabella contiene n + 1 numeri, spazio O(n). n = 45 ora richiede 44 addizioni invece di miliardi di chiamate.

Algoritmo

Se n è 0 o 1, restituisci n.
Crea una tabella di n + 1 numeri con f[0] = 0 e f[1] = 1.
Per i da 2 a n, imposta f[i] = f[i-1] + f[i-2].
Restituisci f[n].

def fib(n):
    if n < 2:
        return n
    f = [0] * (n + 1)  # f[i] will hold F(i)
    f[1] = 1
    for i in range(2, n + 1):
        f[i] = f[i - 1] + f[i - 2]
    return f[n]

Mantieni solo gli ultimi due numeri

Intuizione

Guarda cosa legge il ciclo sulla tabella. Per riempire f[i] servono f[i-1] e f[i-2] e nient’altro di più vecchio, quindi ogni elemento precedente è un peso morto. Usa due variabili invece di una tabella: prev contiene il numero di due passi prima e curr quello di un passo prima.

Inizia con prev = 0 e curr = 1, che sono F(0) e F(1). A ogni passo calcola next = prev + curr, poi fai avanzare la coppia: prev prende il vecchio curr e curr prende next. Per n = 4 la coppia passa da (0, 1) a (1, 1), (1, 2) e (2, 3), e curr = 3 è la risposta.

Il lavoro consiste nelle stesse n-1 addizioni, con tempo O(n) e tre interi in memoria: spazio O(1). L’ordine degli aggiornamenti è importante: se sovrascrivi prev prima di sommarlo, la somma usa il valore sbagliato.

Algoritmo

Se n è 0 o 1, restituisci n.
Imposta prev = 0 e curr = 1.
Ripeti n-1 volte: calcola next = prev + curr, poi imposta prev = curr e curr = next.
Restituisci curr.

def fib(n):
    if n < 2:
        return n
    prev, curr = 0, 1  # F(0) and F(1)
    for _ in range(n - 1):
        prev, curr = curr, prev + curr
    return curr

Trappole e casi limite

Fibonacci è il classico primo problema di programmazione dinamica, e la maggior parte dei bug deriva dalla ricorsione o dai primi due valori.

Consegnare la soluzione con la ricorsione ingenua. Supera i test piccoli, ma poi richiede miliardi di chiamate con n = 45. Memorizza i risultati in una tabella o in due variabili.
Sbagliare i valori iniziali. Qui F(0) = 0 e F(1) = 1, quindi F(2) = 1 e F(10) = 55. Iniziare la sequenza da 1, 1 sposta ogni risultato di un indice.
Creare la tabella senza una protezione per i valori piccoli di n. Per n = 0, una tabella di dimensione n + 1 = 1 non ha spazio per f[1], e scriverci oltrepassa i limiti. Restituisci subito n quando n < 2.
Aggiornare la coppia nell'ordine sbagliato. prev = curr seguito da curr = prev + curr somma il nuovo prev e raddoppia curr. Calcola prima la somma in next, oppure usa un'assegnazione simultanea, se il linguaggio la supporta.
Eseguire un passo di troppo. Un ciclo che calcola anche F(n+1) raggiunge F(46) = 1836311903 al limite, valore che rientra ancora nei 32 bit solo per fortuna. F(47) non ci rientra.

Domande frequenti4

Qual è la complessità temporale della funzione ricorsiva di Fibonacci?

La ricorsione ingenua effettua 2 × F(n+1) - 1 chiamate, un numero che cresce come 1.618^n e che di solito si scrive O(2^n). Per n = 45 sono circa 3.7 × 10^9 chiamate. Memorizzando ogni risultato una sola volta, in una tabella o in due variabili, si riduce a O(n).

Come si risolve Fibonacci con la programmazione dinamica?

Parti dalla ricorrenza F(n) = F(n-1) + F(n-2) e calcola i valori in ordine crescente di n, memorizzandoli uno per uno. Puoi riempire una tabella dal basso verso l’alto oppure mantenere la funzione ricorsiva e memorizzarne nella cache i risultati: questo si chiama memoizzazione. In entrambi i casi ogni valore viene calcolato una sola volta, quindi il lavoro totale è O(n).

È possibile calcolare Fibonacci con spazio O(1)?

Sì. Ogni numero dipende solo dai due precedenti, quindi bastano due variabili. Conserva gli ultimi due valori e falli avanzare a ogni passaggio. Questo richiede un tempo O(n) e uno spazio aggiuntivo O(1).

C'è un modo più veloce di O(n)?

Sì. La matrice [[1, 1], [1, 0]] elevata alla potenza n contiene F(n) nell'angolo in alto a destra, e l'elevamento al quadrato ripetuto calcola quella potenza con O(log n) moltiplicazioni di matrici. Esiste anche una formula chiusa con le potenze del rapporto aureo, ma usa l'aritmetica in virgola mobile e perde precisione man mano che n cresce, quindi sono preferibili i metodi con numeri interi.