문제 토론

문제 목록으로

문제

피보나치 수열을 재귀로 구현할 때와 동적 프로그래밍으로 구현할 때의 시간 복잡도는?

1. O(n), O(n)

2. O(2^n), O(n) (정답)

3. O(n^2), O(n)

4. O(n!), O(n^2)

해설

재귀는 중복 계산으로 O(2^n), 동적 프로그래밍은 메모이제이션으로 O(n)의 시간 복잡도를 가집니다.

로그인하여 토론에 참여하세요.

댓글 (0)

댓글

답글

아직 댓글이 없습니다. 첫 번째 댓글을 작성해보세요!