O(fib n) complexity algorithms?

While watching lecture 1B of the Structure and Interpretation of Computer Programs, there's a function that calculates Fibonacci numbers. The lecturer points out that the time complexity is O(fib n) - I've never seen that before. I've seen it rounded to constant, linear, n+m, quadratic, polynomial, or exponential complexity, but are there any other O(fib n) algorithms or other interesting big O notations that should be looked at or studied?

---

O(fib N) is nothing strange or special - it is exactly the same thing as exponential complexity - it is just that the lecturer did not take the time to spell it out. (You can easily* bound fib(N) with phi^n .)

You don't have to believe me though - you would have a better explanation on Math.stackexchange.

*: I'll clarify what I mean by "easily" - it means that the proof is readily available, for example in that wikipedia article (thanks to the previous answerer that originally gave the link to it).

链接地址: http://www.djcxy.com/p/39912.html

上一篇: 如何计算该算法的大O符号的时间复杂度

下一篇: O（fib n）复杂性算法？