O (n FIB) des algorithmes de complexité?

Question

En regardant conférence 1B de la structure et de l'interprétation des programmes informatiques , il y a une fonction qui calcule les nombres de Fibonacci. Les points de conférencier sur que la complexité est en O (n FIB) - J'ai jamais vu auparavant. Je l'ai vu arrondi à constant, linéaire, n + m, algorithmes ou d'autres notations intéressantes O grandes quadratique, polynomiale, ou la complexité exponentielle, mais y at-il d'autres O (n) fib qui doivent être examinées ou étudiées?

Answer 1

O(fib N) est rien d'étrange ou particulier - c'est exactement la même chose que la complexité exponentielle - il est juste que le conférencier n'a pas pris le temps de le préciser. (Vous pouvez facilement * lié fib(N) avec phi^n.)

Vous ne pas me croire si -. Vous auriez une meilleure explication sur Math.stackexchange

*: Je vais clarifier ce que je veux dire par « facilement » - cela signifie que la preuve est facilement disponible, par exemple dans que l'article de wikipedia (grâce à la answerer précédente qui a donné à l'origine le lien vers elle).