Complessità computazionale della sequenza di Fibonacci

Comprendo la notazione Big-O, ma non so come calcolarla per molte funzioni. In particolare, ho cercato di capire la complessità computazionale della versione ingenua della sequenza di Fibonacci:

int Fibonacci(int n) { if (n <= 1) return n; else return Fibonacci(n - 1) + Fibonacci(n - 2); } 

Qual è la complessità computazionale della sequenza di Fibonacci e come viene calcasting?

Si modella la funzione del tempo per calcolare Fib(n) come sum del tempo per calcolare Fib(n-1) più il tempo per calcolare Fib(n-2) più il tempo per sumrli insieme ( O(1) ).

T(n<=1) = O(1)

T(n) = T(n-1) + T(n-2) + O(1)

Risolvi questa relazione di ricorrenza (usando le funzioni generatrici, per esempio) e finirai con la risposta.

In alternativa, puoi disegnare l'albero di ricorsione, che avrà profondità n e intuitivamente capire che questa funzione è asintoticamente O(2 n ) . Puoi quindi provare la tua congettura per induzione.

Base: n = 1 è ovvio

Supponiamo che T(n-1) = O(2 n-1 ) , quindi

T(n) = T(n-1) + T(n-2) + O(1) che è uguale a

T(n) = O(2 n-1 ) + O(2 n-2 ) + O(1) = O(2 n )

Tuttavia, come notato in un commento, questo non è il limite stretto. Un fatto interessante su questa funzione è che T (n) è asintoticamente uguale al valore di Fib(n) poiché entrambi sono definiti come

f(n) = f(n-1) + f(n-2) .

Le foglie dell'albero ricorsivo torneranno sempre 1. Il valore di Fib(n) è la sum di tutti i valori restituiti dalle foglie nell'albero di ricorsione che è uguale al conteggio delle foglie. Poiché ogni foglia impiegherà O (1) per calcolare, T(n) è uguale a Fib(n) x O(1) . Di conseguenza, il limite stretto per questa funzione è la stessa sequenza di Fibonacci (~ θ(1.6 n ) ). È ansible scoprire questo stretto legame utilizzando le funzioni di generazione come ho menzionato sopra.

Basta chiedere a te stesso quante istruzioni devono essere eseguite per F(n) per completare.

Per F(1) , la risposta è 1 (la prima parte del condizionale).

Per F(n) , la risposta è F(n-1) + F(n-2) .

Quindi quale funzione soddisfa queste regole? Prova un n (a> 1):

a n == a (n-1) + a (n-2)

Dividere per un (n-2) :

a 2 == a + 1

Risolvi per a e ottieni (1+sqrt(5))/2 = 1.6180339887 , altrimenti noto come il rapporto aureo .

Quindi ci vuole tempo esponenziale.

C’è una bella discussione su questo problema specifico al MIT . A pagina 5, indicano che, se si assume che un’aggiunta richiede un’unità computazionale, il tempo richiesto per calcolare Fib (N) è strettamente correlato al risultato di Fib (N).

Di conseguenza, puoi saltare direttamente all’approssimazione molto vicina della serie di Fibonacci:

 Fib(N) = (1/sqrt(5)) * 1.618^(N+1) (approximately) 

e dire, quindi, che la performance peggiore dell’algoritmo ingenuo è

 O((1/sqrt(5)) * 1.618^(N+1)) = O(1.618^(N+1)) 

PS: C’è una discussione sull’espressione di forma chiusa del numero di Nth Fibonacci su Wikipedia se desideri maggiori informazioni.

Sono d’accordo con pgaur e rickerbh, la complessità ricorsiva-fibonacci è O (2 ^ n).

Sono giunto alla stessa conclusione con un ragionamento piuttosto semplicistico, ma credo valido.

Innanzitutto, si tratta di capire quante volte la funzione ricorsiva di fibonacci (F () d’ora in poi) viene chiamata quando si calcola il numero Nth di fibonacci. Se viene chiamato una volta per numero nella sequenza da 0 a n, allora abbiamo O (n), se viene chiamato n volte per ogni numero, quindi otteniamo O (n * n) o O (n ^ 2), e così via.

Quindi, quando F () viene chiamato per un numero n, il numero di volte in cui F () viene chiamato per un dato numero compreso tra 0 e n-1 aumenta man mano che ci avviciniamo a 0.

Come prima impressione, mi sembra che se lo mettiamo in un modo visivo, disegnando un’unità per volta F () viene chiamato per un dato numero, bagnato ottiene una sorta di forma piramidale (cioè, se centriamo le unità orizzontalmente ). Qualcosa come questo:

 n * n-1 ** n-2 **** ... 2 *********** 1 ****************** 0 *************************** 

Ora, la domanda è: quanto è veloce la base di questa piramide che si allarga mentre n cresce?

Prendiamo un caso reale, ad esempio F (6)

 F(6) * <-- only once F(5) * <-- only once too F(4) ** F(3) **** F(2) ******** F(1) **************** <-- 16 F(0) ******************************** <-- 32 

Vediamo che F (0) viene chiamato 32 volte, che è 2 ^ 5, che per questo esempio è 2 ^ (n-1).

Ora, vogliamo sapere quante volte viene chiamata F (x), e possiamo vedere il numero di volte in cui F (0) viene chiamato è solo una parte di quello.

Se spostiamo mentalmente tutte le * dalle linee F (6) a F (2) alla linea F (1), vediamo che le linee F (1) e F (0) ora hanno la stessa lunghezza. Il che significa che i tempi totali F () vengono chiamati quando n = 6 è 2x32 = 64 = 2 ^ 6.

Ora, in termini di complessità:

 O( F(6) ) = O(2^6) O( F(n) ) = O(2^n) 

Puoi espanderlo e avere una visulizzazione

  T(n) = T(n-1) + T(n-2) < T(n-1) + T(n-1) = 2*T(n-1) = 2*2*T(n-2) = 2*2*2*T(n-3) .... = 2^i*T(ni) ... ==> O(2^n) 

È limitato all’estremità inferiore di 2^(n/2) e all’estremità superiore di 2 ^ n (come indicato in altri commenti). E un fatto interessante di tale implementazione ricorsiva è che ha un stretto legame asintotico con Fib (n) stesso. Questi fatti possono essere riassunti:

 T(n) = Ω(2^(n/2)) (lower bound) T(n) = O(2^n) (upper bound) T(n) = Θ(Fib(n)) (tight bound) 

Il tight bound può essere ulteriormente ridotto usando la sua forma chiusa, se lo desideri.

Le risposte alla prova sono buone, ma devo sempre fare alcune iterazioni a mano per convincermi davvero. Quindi ho disegnato un piccolo albero di chiamata sulla lavagna e ho iniziato a contare i nodes. Ho suddiviso i miei conteggi in nodes totali, nodes foglia e nodes interni. Ecco cosa ho ottenuto:

 IN | OUT | TOT | LEAF | INT 1 | 1 | 1 | 1 | 0 2 | 1 | 1 | 1 | 0 3 | 2 | 3 | 2 | 1 4 | 3 | 5 | 3 | 2 5 | 5 | 9 | 5 | 4 6 | 8 | 15 | 8 | 7 7 | 13 | 25 | 13 | 12 8 | 21 | 41 | 21 | 20 9 | 34 | 67 | 34 | 33 10 | 55 | 109 | 55 | 54 

Quello che balza immediatamente fuori è che il numero di nodes foglia è fib(n) . Quello che ha fatto qualche altra osservazione da notare è che il numero di nodes interni è fib(n) - 1 . Pertanto il numero totale di nodes è 2 * fib(n) - 1 .

Poiché si rilasciano i coefficienti quando si classifica la complessità computazionale, la risposta finale è θ(fib(n)) .

Bene, secondo me è O(2^n) come in questa funzione solo la ricorsione sta prendendo il tempo considerevole (divide et impera). Vediamo che, la funzione sopra riportata continuerà in un albero fino a quando le foglie non si avvicinano quando raggiungiamo il livello F(n-(n-1)) cioè F(1) . Quindi, qui quando annotiamo la complessità temporale incontrata a ogni profondità dell’albero, la serie di sumtoria è:

 1+2+4+.......(n-1) = 1((2^n)-1)/(2-1) =2^n -1 

questo è l’ordine di 2^n [ O(2^n) ] .

L’ingenua versione di ricorsione di Fibonacci è esponenziale di design a causa della ripetizione nel calcolo:

Alla radice stai calcolando:

F (n) dipende da F (n-1) e F (n-2)

F (n-1) dipende ancora da F (n-2) e F (n-3)

F (n-2) dipende ancora da F (n-3) e F (n-4)

quindi stai avendo in ogni livello 2 chiamate ricorsive che stanno sprecando un sacco di dati nel calcolo, la funzione del tempo sarà simile a questa:

T (n) = T (n-1) + T (n-2) + C, con costante C

T (n-1) = T (n-2) + T (n-3)> T (n-2) quindi

T (n)> 2 * T (n-2)

T (n)> 2 ^ (n / 2) * T (1) = O (2 ^ (n / 2))

Questo è solo un limite inferiore che per lo scopo della tua analisi dovrebbe essere sufficiente, ma la funzione tempo reale è un fattore di costante dalla stessa formula di Fibonacci e la forma chiusa è noto per essere esponenziale del rapporto aureo.

Inoltre, puoi trovare le versioni ottimizzate di Fibonacci usando la programmazione dynamic come questa:

 static int fib(int n) { /* memory */ int f[] = new int[n+1]; int i; /* Init */ f[0] = 0; f[1] = 1; /* Fill */ for (i = 2; i <= n; i++) { f[i] = f[i-1] + f[i-2]; } return f[n]; } 

Questo è ottimizzato e fa solo n passi ma è anche esponenziale.

Le funzioni di costo sono definite dalla dimensione dell'ingresso al numero di passaggi per risolvere il problema. Quando vedi la versione dynamic di Fibonacci ( n passi per calcolare la tabella) o l'algoritmo più semplice per sapere se un numero è primo ( sqrt (n) per analizzare i divisori validi del numero). potreste pensare che questi algoritmi siano O (n) o O (sqrt (n)), ma semplicemente non è vero per il seguente motivo: L'input per il vostro algoritmo è un numero: n , usando la notazione binaria la dimensione di input per un intero n è log2 (n) quindi esegue un cambiamento variabile di

 m = log2(n) // your real input size 

scoprire il numero di passaggi in funzione della dimensione di input

 m = log2(n) 2^m = 2^log2(n) = n 

quindi il costo dell'algoritmo in funzione della dimensione dell'input è:

 T(m) = n steps = 2^m steps 

e questo è il motivo per cui il costo è esponenziale.

Questo funziona meglio:

 unsigned int Fib(unsigned int n) { // first Fibonaci number is Fib(0) // second one is Fib(1) and so on // unsigned int m; // m + current_n = original_n unsigned int a = 1; // Fib(m) unsigned int b = 0; // Fib(m-1) unsigned int c = 0; // Fib(m-2) while (n--) { c = b; b = a; a = b+c; } return a; }