다음 중 컴퓨터 프로그래밍을 통하여 문제를 해결하는데 최적의 시간복잡도… | [7급 국가직 자료구조론] 12년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 12년 1회차
다음 중 컴퓨터 프로그래밍을 통하여 문제를 해결하는데 최적의 시간복잡도가 가장 큰 것은?
1
임의의 정수 100,000개를 선택정렬(selection sort)로 정렬하는 문제
2
정렬된 100,000개의 정수에서 임의의 정수를 이진탐색하는 문제
3
반복 호출로 피보나치수열 , , , … 에서 값을 구하는 문제
4
재귀호출로 하노이 탑(tower of Hanoi)의 100,000개 원판 이동 문제
해설
하노이 탑의 원판 이동 횟수는 로 지수 시간이므로 시간복잡도가 가장 크다.
원판 n개를 옮기려면 n−1개를 두 번 옮기고 가장 큰 원판을 한 번 옮기므로 , 즉 이다.
- 선택정렬은 로 다항 시간이다.
- 정렬된 배열의 이진탐색은 이다.
- 반복문으로 피보나치 수를 구하면 이다.
오류나 개정된 내용이 보이면 알려주세요