O (fib n) 복잡도 알고리즘?

Question

lecture 1B of the Structure and Interpretation of Computer Programs을 보면서 피보나치 수를 계산하는 기능이 있습니다. 강사는 시간 복잡도가 O (fib n)라고 지적합니다. 전에는 본 적이 없었습니다. 선형, n + m, 2 차, 다항식 또는 지수 복잡도로 반올림 한 것을 보았지만 다른 O (fib n) 알고리즘이나 다른 흥미로운 큰 O 표기법이 있습니까?

Answer 1

O(fib N)은 기이 한 복잡성과 똑같습니다. 강사가 철자를 쓰지 않은 것입니다. (fib(N)을 phi^n으로 쉽게 묶을 수 있습니다.)

당신은 나를 믿을 필요가 없습니다. Math.stackexchange에 대한 더 나은 설명이 있습니다.

* : "쉽게"의미한다는 것을 분명히 할 것입니다 - 이는 증명이 쉽게 이용 가능하다는 것을 의미합니다 (예 : that wikipedia article).