c/c++ 피보나치 수열 일반항 구하기와 시간 복잡도
알고리즘 2012. 11. 19. 20:17 |보통 피보나치 수열의 일반항은 a0 부터 차례대로 구하는 방법이 있다.
이 방법은 time complexcity O(n) 이다.
하지만, 피보나치 수열의 일반항[1]을 이용하면 time complexity 를 O(log n) 으로 계산 할 수 있다.[2]
물론, float point 의 곱셈 계산이 필요하므로, n 이 작으면 위 방법에 비해 시간이 더 많이 소요될 수 있다.
(아마 보통은 아래 방법이 더 오래 걸릴 것이다.)
게다가 double 형 타입의 계산 오차로 인해 n 이 충분히 크다면 대략 오차가 발생한다.
(테스트 해 보니 n=75 까지 잘 계산 되고, n=76 에서 1 오차가 발생함.)
결론적으론 첫 번째 방법이 더 좋다 ㅡㅡ;
references :
[1] http://en.wikipedia.org/wiki/Fibonacci_number
[2] http://stackoverflow.com/questions/5231096/time-complexity-of-power