<div><br></div> <div> <div style="text-align:left;"><img src="http://thimg.todayhumor.co.kr/upfile/201407/1406377567RtOnpeqOF66YD.png" width="596" height="402" alt="fibonacci_source.PNG" style="border:none;"></div> <div style="text-align:left;"><img src="http://thimg.todayhumor.co.kr/upfile/201407/1406377566LG1jimIBURBGy9Objx3EU9fzZxtQWp.png" width="734" height="621" alt="fibonacci_memory.PNG" style="border:none;"></div> <div style="text-align:left;"><img src="http://thimg.todayhumor.co.kr/upfile/201407/1406377566nRcd3qsfn4QicAQLM7jH.png" width="367" height="155" alt="fibonacci_result.PNG" style="border:none;"></div> <div style="text-align:left;"><br></div> <div style="text-align:left;"><br></div> <div style="text-align:left;">연산은 싱글스레드라 가정하겠습니다.</div> <div style="text-align:left;"><br></div> <div style="text-align:left;">궁금증이 생겨서 간단히 자바로 간단한 피보나치 재귀함수를 짜서 테스트를 해봤습니다</div> <div style="text-align:left;"><br></div> <div style="text-align:left;">소스코드 보시면 연산량이 O(2^n) 으로 증가합니다.</div> <div style="text-align:left;"><br></div> <div style="text-align:left;">입력값에 45를 집어넣었으므로 연산량이 2^45 , 대략 10^4 * 2^5 = 32테라정도가 나옵니다.</div> <div style="text-align:left;"><br></div> <div style="text-align:left;">2.5Ghz의 클럭으로 10000초는 걸려야 한다는게 이론적인 계산인데, 실제로는 대략 14초 정도가 나오네요</div> <div style="text-align:left;"><br></div> <div style="text-align:left;">자바 VM에서 메모이제이션같은 알고리즘을 자동적으로 적용해서 연산량이 줄어드는건지 제 이론이 틀린건지 궁금합니다.</div> <div style="text-align:left;"><br></div> <div style="text-align:left;">덧붙이자면, 입력값 40정도에서 1초가 나왔고, 입력값이 1 증가하면 1.7배씩 증가하는것같습니다.</div> <div style="text-align:left;"><br></div> <div style="text-align:left;">1.7^45 = 2.3E10 이네요.</div> <div style="text-align:left;"><br></div><br></div>
댓글 분란 또는 분쟁 때문에 전체 댓글이 블라인드 처리되었습니다.