O (FIB n) algoritmos de complejidad?

Question

Mientras está viendo 1B conferencia de la estructura e interpretación de programas de ordenador , hay una función que calcula los números de Fibonacci. Los puntos conferenciante que la complejidad del tiempo es O (n fib) - nunca he visto eso antes. Lo he visto redondeado al constante, lineal, n + m, cuadrática, polinómica, exponencial o complejidad, pero ¿existen otros algoritmos O (fib n) u otros notaciones grandes O interesantes que deben mirarse o estudiado?

Answer 1

O(fib N) es nada extraño o especial - que es exactamente lo mismo que la complejidad exponencial - es sólo que el profesor no se toman el tiempo para explicarla. (Puede fácilmente * fib(N) atado con phi^n.)

No tienes que creerme aunque -. Usted tendría una mejor explicación sobre Math.stackexchange

*: Voy a aclarar lo que quiero decir con "facilidad" - significa que la prueba está fácilmente disponible, por ejemplo en artículo de Wikipedia que (gracias a la contestadora anterior que originalmente dio el enlace a ella).