O algoritmi di complessità (n FIB)?

Question

Mentre si guarda conferenza 1B della Struttura e Interpretazione dei programmi per elaboratore , c'è una funzione che calcola i numeri di Fibonacci. I punti docente fuori che la complessità temporale è O (n fib) - non ho mai visto prima. L'ho visto arrotondato al costante, lineare, n + m, quadratica, polinomiale, o la complessità esponenziale, ma ci sono dei altri algoritmi O (fib n) o altre notazioni interessanti Big O che dovrebbe essere consultato la pagina o studiato?

Answer 1

O(fib N) c'è niente di strano o di speciale - è esattamente la stessa cosa di complessità esponenziale - è solo che il docente non ha preso il tempo per chiarirne il significato. (Si può facilmente * fib(N) con phi^n legato.)

Non hai credermi anche se -. Si avrebbe una spiegazione migliore sulle Math.stackexchange

*: io chiarire cosa intendo per "facilmente" - vuol dire che la prova è prontamente disponibile, per esempio in questo articolo wikipedia (grazie a chi ha risposto precedente che in origine ha dato il link ad esso).