연산은 싱글스레드라 가정하겠습니다.

궁금증이 생겨서 간단히 자바로 간단한 피보나치 재귀함수를 짜서 테스트를 해봤습니다

소스코드 보시면 연산량이 O(2^n) 으로 증가합니다.

입력값에 45를 집어넣었으므로 연산량이 2^45  , 대략 10^4 * 2^5 = 32테라정도가 나옵니다.

2.5Ghz의 클럭으로 10000초는 걸려야 한다는게 이론적인 계산인데, 실제로는 대략 14초 정도가 나오네요

자바 VM에서 메모이제이션같은 알고리즘을 자동적으로 적용해서 연산량이 줄어드는건지 제 이론이 틀린건지 궁금합니다.

덧붙이자면,  입력값 40정도에서 1초가 나왔고, 입력값이 1 증가하면 1.7배씩 증가하는것같습니다.

1.7^45 = 2.3E10 이네요.