알고리즘간의 실행시간을 비교

목차

□ 프로젝트의 목적 : 알고리즘1.6(fib1)과 1.7(fib2)을 컴퓨터에 구현하라.

□ Source Code(소스코드1) - <FIB1>

□ Source Code(소스코드2) - <FIB2>

□ Execution Result(실행결과1) - <FIB1>

□ Execution Result(실행결과1) - <FIB1>

□ 비교그래프

본문내용

225초
0초
44
361초
0초
45
583초
0초
46
942초
0초
47
1557초
0초
48
2494초
0초
49
4017초
0초
50
6215초
0초
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
□ 검토 및 토의사항
FIB1함수와 FIB2함수의 실행시간이 n이 커질수록 점점 더 격차가 심해지고 있다. 이는 FIB1함수가 재귀 알고리즘을 토대로 짜여져 있기 때문이다. 재귀 알고리즘이 가지고 있는 문제점은 같은 값을 중복해서 계산하는 것이다. 예를 들어 FIB(2)는 FIB(5)를 계산하기 위해 세 번 중복 계산하게 된다. 만약 FIB2함수처럼 값을 계산할 때 그 값을 배열에 저장한다면 나중에 필요할 때마다 다시 계산할 필요가 없을 것이다. 사실 FIB2함수는 매번 반복할 때마다 가장 최근 2개의 항만을 필요로 하기 때문에 배열 f를 사용하지 않고도 작성할 수 있지만 배열을 사용하면 알고리즘을 더 명확히 표현할 수 있다. 두 함수의 실행 시간 비교를 통해 FIB1함수는 n이 작은 경우를 제외하고 기다릴 수 없는 만큼의 시간이 걸린다는 사실을 알았고 반면에 FIB2함수가 사용하는 알고리즘은 n번째 피보나찌 항을 거의 즉석에서 계산하는 것을 알게 되었다. 컴퓨터의 계산속도가 빨라지는 것과 무관하게 알고리즘의 효율성이 왜 중요한 고려사항이 되는지를 이 비교를 통해 명확히 알 수 있다. 그리고 나의 경우 FIB1을 실행하는 도중 컴퓨터로 다른 작업을 병행해서 그런지는 몰라도 예상했던 시간보다 무척 오래걸리는(1시간이상) 실행 시간결과가 나왔다.

키워드

fib1,   fib2,   실행시간,   비교,   알고리즘