다음 피보나치 수열의 n번째 항을 계산하는 알고리즘에 대한 설명으로 옳… | [7급 국가직 알고리즘] 23년 1회차 기출문제 상세 페이지
1[7급 국가직 알고리즘] 23년 1회차
다음 피보나치 수열의 n번째 항을 계산하는 알고리즘에 대한 설명으로 옳지 않은 것은? (단, n ≥ 0이다)int fib(n) {
if (n == 0)
return 0;
if (n == 1)
return 1;
return fib(n – 1) + fib(n – 2);
}1
fib(7) 호출 시, fib(3)은 5번 호출된다.
2
알고리즘의 시간 복잡도는 이다.3
알고리즘의 점화식은 이다.4
반복문을 사용하여 알고리즘 성능을 개선할 수 있다.
해설
재귀 피보나치는 호출이 지수적으로 늘어나므로 시간 복잡도가 라는 설명이 옳지 않다.
fib(n)은 fib(n-1)과 fib(n-2)를 모두 다시 호출해 같은 값을 중복 계산하므로, 호출 횟수가 피보나치 수에 비례해 늘어나는 지수 시간( 상한)이 된다.
- fib(4)·fib(5)·fib(6)·fib(7)을 호출할 때 fib(3)의 호출 횟수는 1, 2, 3, 5회로 피보나치 수열처럼 늘어 fib(7)에서 5회가 맞다.
- 제시된 점화식은 코드의 두 기저 조건과 재귀 호출을 그대로 옮긴 것으로 옳다.
- 반복문으로 직전 두 항만 유지하며 계산하면 으로 성능이 개선된다.
오류나 개정된 내용이 보이면 알려주세요