O (fib n) Komplexität Algorithmen?

Question

Beim Betrachten Vortrag 1B der Struktur und Interpretation von Computerprogrammen , gibt es eine Funktion, die Fibonacci-Zahlen berechnet. Die Dozentin weist darauf hin, dass die Zeitkomplexität O (fib n) - Ich habe noch nie gesehen, dass vor. Ich habe es gesehen konstant gerundet, linear, n + m, quadratisch, Polynom oder exponentielle Komplexität, aber gibt es andere O (fib n) Algorithmen oder andere interessante große O-Notationen, die an oder untersucht betrachtet werden sollte?

Answer 1

O(fib N) ist nichts Ungewöhnliches oder besondere - es ist genau das gleiche wie exponentielle Komplexität - es ist nur, dass der Vortragende nicht die Zeit nehmen, kam es zu buchstabieren. (Sie können leicht * gebunden fib(N) mit phi^n.)

Sie müssen mir nicht glauben, aber -. Sie eine bessere Erklärung haben würde auf Math.stackexchange

*: Ich werde erklären, was ich mit „leicht“ bedeuten - es bedeutet, dass der Beweis leicht verfügbar ist, zum Beispiel in , dass wikipedia-Artikel (dank den vorherigen Antworter, dass ursprünglich die Verbindung zu ihm gegeben haben).