Chiuso . Questa domanda richiede dettagli o chiarezza . Attualmente non accetta risposte.
Commenti
- La tua domanda include già una risposta completa al problema originale ma nessuna domanda su questa risposta. Pertanto, possono rimanere solo le risposte " sì / no ", che non aiutano né te né i futuri visitatori. Leggi le meta discussioni correlate qui e qui e modifica la tua domanda di conseguenza, ad es. formulando una domanda specifica su un singolo elemento della tua risposta di cui non sei sicuro. Se desideri solo un feedback generale, ti invitiamo a farci visita nella Chat di informatica .
- @DavidRicherby Allora prova a non guardare il mio rispondi e rispondi, se puoi. Ho adorato questo sito fino a quando tutti hanno iniziato a trovare i difetti delle domande poste piuttosto che aiutare quello con la domanda.
- Da quello che penso tu stia cercando di chiedere, sì $ T (n) $ sarebbe in $ O (2 ^ n) $ ma ' hai un limite superiore più stretto con $ T (n) \ in O (\ phi ^ n) $ dove $ \ phi = \ frac {1+ \ sqrt {5}} {2} $
- Inoltre, luso di immagini da solo non è un buon stile qui. Per favore trascrivi gli elementi di testo – nota che puoi usare LaTeX qui (tramite MathJax).
- La tua query non è nemmeno sbagliata. La " complessità temporale della sequenza di Fibonacci " non è una cosa. Ci sono due cose significative da chiedere qui: 1) Qual è la crescita asintotica della sequenza di Fibonacci (in $ \ Theta $)? 2) Qual è il tempo di esecuzione asintotico di questo algoritmo che calcola i numeri di Fibonacci? – Immagino volessi dire 2). Per questo, abbiamo un paio di domande di riferimento e anche per la risoluzione delle ricorrenze .
Risposta
Lanalisi non è accurata sebbene il risultato sia corretto. Potresti scriverlo in modo più accurato sostituendo $ = $ con $ \ le $
$ T (n) \ le c (1 + 2 + .. + 2 ^ {n-1}) $ ($ \ le $ poiché non tutti i livelli hanno lo stesso numero di figli, considera il percorso più destrorso, n diminuisce di $ 2 $ ogni passo).
In effetti unanalisi più attenta può farti diventare un limite più stretto poiché menzionato nel commento. Lidea è che il tempo $ T (n) $ viene calcolato con $ T (n-1) + T (n-2) $ allo stesso modo delleffettivo fibonacci $ F (n) $, e poiché $ F (n ) = O (\ phi ^ n) $ per $ \ phi = (1+ \ sqrt {5}) / 2 $ come forma chiusa.
Quindi $ T (n) = O (\ phi ^ n) $ che è leggermente inferiore a $ 2 ^ n $
Commenti
- Per la seconda parte, è necessario essere consapevoli del termine di pedaggio aggiuntivo $ c $ nella ricorrenza di $ T $. La ricorrenza per $ F $ conta solo le foglie, ma quella di $ T $ conta tutti i nodi. Non è sempre vero che il numero di foglie domina asintoticamente, cfr. metodo dellalbero di ricorsione.