Fechado . Esta pergunta precisa de detalhes ou clareza . Atualmente não está aceitando respostas.
Comentários
- Sua pergunta já inclui uma resposta completa para o problema original, mas nenhuma pergunta sobre esta resposta. Portanto, apenas as respostas " sim / não " podem permanecer, não ajudando você nem os futuros visitantes. Leia as metatodiscussões relacionadas aqui e aqui e ajuste sua pergunta de acordo, por exemplo, formulando uma pergunta específica sobre um único elemento de sua resposta sobre o qual você não tem certeza. Se você deseja apenas um feedback geral, fique à vontade para nos visitar no Bate-papo da ciência da computação .
- @DavidRicherby Bem, tente não olhar para o meu responda e responda, se puder. Adorei este site até que todos começaram a encontrar falhas nas perguntas feitas, em vez de ajudar quem tinha a pergunta.
- Pelo que acho que você está tentando perguntar, sim, $ T (n) $ estaria em $ O (2 ^ n) $ mas você ' d tem um limite superior mais estreito com $ T (n) \ in O (\ phi ^ n) $ onde $ \ phi = \ frac {1+ \ sqrt {5}} {2} $
- Além disso, usar apenas imagens não é um bom estilo aqui. Transcreva os elementos de texto – observe que você pode usar LaTeX aqui (via MathJax).
- Sua consulta não está errada. A " complexidade de tempo da sequência de Fibonacci " não é uma coisa. Há duas coisas significativas a se perguntar aqui: 1) Qual é o crescimento assintótico da sequência de Fibonacci (em $ \ Theta $)? 2) Qual é o tempo de execução assintótico desse algoritmo que calcula os números de Fibonacci? – Eu acho que você quis dizer 2). Para isso, temos algumas perguntas de referência e também para resolver recorrências .
Resposta
A análise não é precisa, embora o resultado seja correto. Você poderia escrever com mais precisão substituindo $ = $ por $ \ le $
$ T (n) \ le c (1 + 2 + .. + 2 ^ {n-1}) $ ($ \ le $ uma vez que nem todos os níveis têm o mesmo número de filhos, considere o caminho mais destro, n está diminuindo em $ 2 $ a cada passo).
De fato, uma análise mais cuidadosa pode te ajudar a estabelecer um limite mais estreito, pois mencionado no comentário. A ideia é que o tempo $ T (n) $ é calculado com $ T (n-1) + T (n-2) $ da mesma forma que o fibonacci real $ F (n) $, e desde $ F (n ) = O (\ phi ^ n) $ para $ \ phi = (1+ \ sqrt {5}) / 2 $ como a forma fechada.
Assim, $ T (n) = O (\ phi ^ n) $ que é ligeiramente menor que $ 2 ^ n $
Comentários
- Para a segunda parte, é preciso estar atento ao termo de pedágio adicional $ c $ na recorrência de $ T $. A recorrência para $ F $ conta somente folhas, mas a de $ T $ conta todos os nós. Nem sempre é o caso que o número de folhas predomina assintoticamente, cf. método de árvore de recursão.