c/c++ 피보나치 수열 일반항 구하기와 시간 복잡도

보통 피보나치 수열의 일반항은 a0 부터 차례대로 구하는 방법이 있다.

이 방법은 time complexcity O(n) 이다.

uint64 fibonacci(int n) { if (n == 0) return 0; if (n == 1) return 1; uint64 sum; uint64 temp1 = 0; uint64 temp2 = 1; for (int i = 1; i < n; i++) { sum = temp1 + temp2; temp1 = temp2; temp2 = sum; } return sum; }

 

 

하지만, 피보나치 수열의 일반항[1]을 이용하면 time complexity 를 O(log n) 으로 계산 할 수 있다.[2]

물론, float point 의 곱셈 계산이 필요하므로, n 이 작으면 위 방법에 비해 시간이 더 많이 소요될 수 있다.

(아마 보통은 아래 방법이 더 오래 걸릴 것이다.)

게다가 double 형 타입의 계산 오차로 인해 n 이 충분히 크다면 대략 오차가 발생한다.

(테스트 해 보니 n=75 까지 잘 계산 되고, n=76 에서 1 오차가 발생함.)

#include <cmath> #define ROOT_5 2.2360679774997896964091736687313 using namespace std; uint64 fibonacci(int n) { double res = (pow((1+ROOT_5)/2, n) - pow((1-ROOT_5)/2, n)) / ROOT_5; return (uint64)(res+.5); }

 

결론적으론 첫 번째 방법이 더 좋다 ㅡㅡ;

 

references :

[1] http://en.wikipedia.org/wiki/Fibonacci_number

[2] http://stackoverflow.com/questions/5231096/time-complexity-of-power