O (FIB n) algoritmos de complejidad?
-
30-09-2019 - |
Pregunta
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?
Solución
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).