O (fib n) Komplexitätsalgorithmen?

Question

Beim Ansehen lecture 1B of the Structure and Interpretation of Computer Programs gibt es eine Funktion, die Fibonacci-Zahlen berechnet. Der Dozent weist darauf hin, dass die Zeitkomplexität O (fib n) ist - das habe ich noch nie zuvor gesehen. Ich habe gesehen, dass es auf konstante, lineare, n + m, quadratische, polynomische oder exponentielle Komplexität gerundet wurde, aber gibt es noch andere O (fib n) -Algorithmen oder andere interessante große O-Notationen, die betrachtet oder studiert werden sollten?

Answer 1

O(fib N) ist nichts Seltsames oder Spezielles - es ist genau dasselbe wie exponentielle Komplexität - es ist nur so, dass der Dozent sich nicht die Zeit genommen hat, es zu buchstabieren. (Sie können einfach mit phi^n binden.)

Sie müssen mir nicht glauben - Sie hätten eine bessere Erklärung auf Math.stackexchange.

*: Ich werde klarstellen, was ich mit "leicht" meine - es bedeutet, dass der Beweis leicht verfügbar ist, zum Beispiel in that wikipedia article (danke an den vorherigen Beantworter, der ursprünglich den Link dazu gab).