다음은 재귀 호출을 이용하여 피보나치(Fibonacci) 수열값을 찾는… | [7급 국가직 알고리즘] 25년 1회차 기출문제 상세 페이지

1[7급 국가직 알고리즘] 25년 1회차

다음은 재귀 호출을 이용하여 피보나치(Fibonacci) 수열값을 찾는 파이썬 코드이다. 이 코드의 시간 복잡도는? (단, n은 0 이상의 정수이다)def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n - 1) + fib(n - 2)

 $\mathrm{O}(n)$

 $\mathrm{O}(n^2)$

 $\mathrm{O}(2^n)$

 $\mathrm{O}(\log n)$

해설

이 재귀 피보나치 함수의 시간 복잡도는 지수 시간  $\mathrm{O}(2^n)$ 이다.
한 번 호출될 때마다 fib(n-1)과 fib(n-2)를 다시 호출하고 계산 결과를 저장하지 않으므로 같은 값을 중복 계산한다.
 $T(n) = T(n-1) + T(n-2) + \mathrm{O}(1)$ 이므로 호출 수가 피보나치 수처럼 늘어나며, 상한은  $\mathrm{O}(2^n)$ 이다.
 $\mathrm{O}(n)$ 은 계산값을 저장하는 동적 프로그래밍이나 반복문으로 구현했을 때의 복잡도이다.
 $\mathrm{O}(n^2)$ 은 호출 트리가 매 단계 두 갈래로 갈라지는 증가 속도를 반영하지 못한다.
 $\mathrm{O}(\log n)$ 은 행렬 거듭제곱을 이용한 방법의 복잡도이다.

오류나 개정된 내용이 보이면 알려주세요

이어서 풀어보기

[7급 국가직 알고리즘] 25년 1회차 25문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요

비슷한 기출

7급 국가직 알고리즘 기출문제 암기장 전체 보기

💬 자격증 스터디 커뮤니티헷갈리는 문제, 같이 준비하는 사람들에게 물어보세요

→