complessità computazionale di Fibonacci

https://stackoverflow.com/questions/360748

21-08-2019
|

Domanda

Capisco notazione O-grande, ma non so come calcolarlo 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 calcolato?

Soluzione

È modellare la funzione di tempo per calcolare Fib(n) come somma del tempo per calcolare Fib(n-1) più il tempo per calcolare Fib(n-2) più il tempo di aggiungere insieme (O(1)). Ciò presuppone che le ripetute valutazioni della stessa T(n<=1) = O(1) prendere contemporaneamente -. Cioè senza memoization è uso

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

n

A risolvere questa relazione di ricorrenza (utilizzando la generazione di funzioni, per esempio) e si finirà con la risposta.

In alternativa, è possibile disegnare l'albero di ricorsione, che avrà la profondità O(2 e intuitivo capire che questa funzione è asintoticamente ) ^{n = 1} T(n-1) = O(2. È quindi possibile dimostrare la vostra congettura per induzione.

Base: n-1 è ovvio

Si supponga T(n) = O(2 ^{) + O(2} n-2, quindi

) + O(1) = O(2 che è uguale a

f(n) = f(n-1) + f(n-2) ^T(n) Fib(n) x O(1) ^θ(1.6 <=> ^<=> <=>

Tuttavia, come osservato in un commento, questa non è la tenuta legata. Un fatto interessante di questa funzione è che il T (n) è asintoticamente stesso come valore di <=> poiché entrambi sono definiti come

<=>.

Le foglie dell'albero di ricorsione restituisce sempre 1. Il valore di <=> è somma di tutti i valori restituiti dalle foglie nell'albero di ricorsione che è uguale al conteggio delle foglie. Poiché ogni foglia assumerà O (1) per calcolare, <=> è pari a <=>. Di conseguenza, la stretta vincolato per questa funzione è la sequenza di Fibonacci stessa (~ <=> ^<=> <=>). Potete trovare questo stretto vincolati utilizzando funzioni generatrici come avevo già detto.

Altri suggerimenti

Basta chiedersi quante dichiarazioni deve eseguire per F(n) per completare.

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

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

Quindi, quale funzione soddisfa queste regole? Provare con un ⁿ (a> 1):

una ⁿ == un ^(n-1) + un ^(n-2)

Dividere attraversato da una ^(n-2):

un ² == un segnalino + 1

risolvere per (1+sqrt(5))/2 = 1.6180339887 e si ottiene <=>, altrimenti noto come il rapporto aureo .

Quindi, ci vuole tempo esponenziale.

C'è una bella discussione di questo problema specifico oltre al MIT . A pagina 5, fanno il punto che, se si assume che un'aggiunta prende un'unità di calcolo, il tempo necessario per calcolare Fib (N) è molto strettamente legato al risultato della Fib (N).

Di conseguenza, è possibile saltare direttamente al molto vicino approssimazione della serie di Fibonacci:

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

e dire, quindi, che la peggiore performance caso l'algoritmo ingenuo è

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

PS: C'è una discussione sulla chiuso sotto forma di espressione del numero di Fibonacci ennesimo sopra a Wikipedia se vuoi ulteriori informazioni.

Sono d'accordo con pgaur e rickerbh, la complessità di recursive-Fibonacci è O (2 ^ n).

Sono giunto alla stessa conclusione da un po 'semplicistica, ma credo che il ragionamento ancora valido.

Per prima cosa, è tutta una questione di capire quante volte la funzione Fibonacci ricorsiva (F () d'ora in poi) viene chiamato nel calcolo del numero di Fibonacci ennesimo. Se viene chiamato una volta per ogni numero della sequenza da 0 a n, allora abbiamo O (n), se viene chiamato n volte per ogni numero, allora otteniamo O (n * n), o O (n ^ 2), e così via.

Così, 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 cresce mentre ci avviciniamo 0.

Come prima impressione, mi sembra che se mettiamo in modo visivo, disegnando un'unità per volta F () viene chiamato per un dato numero, bagnato ottenere una sorta di forma piramidale (cioè, se centrare unità orizzontalmente). Qualcosa di simile a questo:

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

Ora, la domanda è, quanto velocemente è la base di questa piramide allargando come n cresce?

Diamo un caso reale, per 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 F (0) viene chiamato 32 volte, che è 2 ^ 5, che per questo caso campione è 2 ^ (n-1).

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

Se mentalmente spostare tutti s 'dalla F del * (6) a F (2) linee in F (1) linea, vediamo che F (1) e F (0) linee sono ora uguali in lunghezza. Il che significa, tempi totali F () viene chiamata quando n = 6 è 2x32 = 64 = 2 ^ 6.

Ora, in termini di complessità:

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

È possibile espandere e avere una visualizzazione

     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(n-i)
     ...
     ==> O(2^n)

E 'delimitata all'estremità inferiore da 2^(n/2) e sull'estremità superiore del 2 ^ n (come notato in altri commenti). E un fatto interessante di questa implementazione ricorsiva è che ha un asintotico stretto rilegato di 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)

La stretta legato può essere ridotta ulteriormente utilizzando la sua rel="noreferrer"> , se volete.

Le risposte di prova sono buoni, ma ho sempre dovuto fare un paio di iterazioni a mano per convincere veramente me stesso. Così ho disegnato fuori un piccolo albero di chiamata sulla mia lavagna, e ha iniziato a contare i nodi. Ho diviso i miei conteggi fuori in nodi totali, nodi foglia, e nodi interni. Ecco quello che 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

Ciò che salta subito fuori è che il numero di nodi foglia è fib(n). Che ha preso un paio di iterazioni da notare è che il numero di nodi interni è fib(n) - 1. Quindi il numero totale di nodi è 2 * fib(n) - 1.

Dal momento che si rilascia i coefficienti nella classificazione di complessità computazionale, la risposta finale è θ(fib(n)).

complessità temporale dell'algoritmo ricorsivo può essere meglio stimato disegnando albero di ricorsione, in questo caso la relazione di ricorrenza per disegnare albero di ricorsione sarebbe T (n) = T (n-1) + T (n-2) + O (1 ) notare che ogni passaggio richiede O (1) nel senso costante di tempo, dal momento che solo un confronto per verificare il valore di n in se albero block.Recursion sarà simile

          n
   (n-1)      (n-2)
(n-2)(n-3) (n-3)(n-4) ...so on

Qui diciamo ogni livello di albero di cui sopra è indicato con i quindi,

i
0                        n
1            (n-1)                 (n-2)
2        (n-2)    (n-3)      (n-3)     (n-4)
3   (n-3)(n-4) (n-4)(n-5) (n-4)(n-5) (n-5)(n-6)

Diciamo al particolare valore di i, le estremità dell'albero, questo caso sarebbe quando n-i = 1, quindi i = n-1, il che significa che l'altezza dell'albero è n-1. Ora lascia per vedere quanto lavoro è fatto per ciascuna delle n strati in tree.Note che ogni passaggio richiede O (1) tempo indicato nella relazione di ricorrenza.

2^0=1                        n
2^1=2            (n-1)                 (n-2)
2^2=4        (n-2)    (n-3)      (n-3)     (n-4)
2^3=8   (n-3)(n-4) (n-4)(n-5) (n-4)(n-5) (n-5)(n-6)    ..so on
2^i for ith level

poiché i = n-1 è l'altezza di lavoro albero fatto a ogni livello sarà

i work
1 2^1
2 2^2
3 2^3..so on

Quindi lavoro totale svolto sommerà del lavoro svolto ad ogni livello, per cui sarà 2 ^ 0 + 2 ^ 1 + 2 ^ 2 + 2 ^ 3 ... + 2 ^ (n-1) da i = n -1. Per serie geometrica tale somma è 2 ^ n, dunque tempo complessità totale qui è O (2 ^ n)

Bene, secondo me è O(2^n) come in questa funzione solo ricorsione sta prendendo il tempo considerevole (divide et impera). Vediamo che, la funzione di cui sopra continuerà in un albero fino a quando le foglie sono approcci quando si raggiunge il livello F(n-(n-1)) cioè F(1). Così, qui quando abbiamo annotare la complessità temporale incontrato a ciascuna profondità di albero, la serie sommatoria è:

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

che è dell'ordine di 2^n [ O(2^n) ].

http://www.ics.uci.edu/~eppstein /161/960109.html

tempo (n) = 3F (n) - 2

La versione ricorsione naive di Fibonacci è esponenziale di progettazione grazie alla ripetizione nel calcolo:

Alla radice che si sta Computing:

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

F (n-1) dipende F (n-2) di nuovo e F (n-3)

F (n-2) dipende F (n-3) di nuovo e F (n-4)

, allora si hanno ad ogni livello 2 chiamate ricorsive che sprecano un sacco di dati per il calcolo, la funzione di tempo sarà simile a questa:

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

T (n-1) = T (n-2) + T (n-3)> T (n-2), allora

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

...

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

Questa è solo un limite inferiore che, ai fini della vostra analisi dovrebbe essere sufficiente, ma la funzione in tempo reale è un fattore di una costante con la stessa formula di Fibonacci e la chiuso si caratterizza per essere esponenziale del rapporto aureo.

In aggiunta, si possono trovare versioni di Fibonacci utilizzano programmazione dinamica come questo ottimizzata:

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];
}

ottimizzato e fare solo n passaggi ma è anche esponenziale.

Le funzioni di costo sono definite dalla grandezza di ingresso al numero di passaggi per risolvere il problema. Quando si vede la versione dinamica di Fibonacci ( n passi per calcolare la tabella) o l'algoritmo più semplice per sapere se un numero è primo ( sqrt (n) per analizzare la validità divisori del numero). si potrebbe pensare che questi algoritmi sono O (n) o O (sqrt (n)) , ma questo non è vero per il seguente motivo: L'ingresso al vostro algoritmo è un numero: n , utilizzando la notazione binaria la dimensione di ingresso per un intero n è log2 (n) , quindi fare un cambio variabile della

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

lasciare scoprire il numero di passi in funzione della dimensione di input

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

allora il costo del vostro algoritmo in funzione della dimensione di ingresso è:

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

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

Autorizzato sotto: CC-BY-SA insieme a attribuzione

Non affiliato a StackOverflow