다음 중 컴퓨터 프로그래밍을 통하여 문제를 해결하는데 최적의 시간복잡도… | [7급 국가직 자료구조론] 12년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 12년 1회차
다음 중 컴퓨터 프로그래밍을 통하여 문제를 해결하는데 최적의 시간복잡도가 가장 큰 것은?
1
임의의 정수 100,000개를 선택정렬(selection sort)로 정렬하는 문제
2
정렬된 100,000개의 정수에서 임의의 정수를 이진탐색하는 문제
3
반복 호출로 피보나치수열 F0F_{0}, F1F_{1}, F2F_{2}, … 에서 F100000F_{100000} 값을 구하는 문제
4
재귀호출로 하노이 탑(tower of Hanoi)의 100,000개 원판 이동 문제
해설

하노이 탑의 원판 이동 횟수는 2n−12^{n}-1로 지수 시간이므로 시간복잡도가 가장 크다.

원판 n개를 옮기려면 n−1개를 두 번 옮기고 가장 큰 원판을 한 번 옮기므로 T(n)=2T(n−1)+1T(n) = 2T(n-1) + 1, 즉 O(2n)O(2^{n})이다.

  • 선택정렬은 O(n2)O(n^{2})로 다항 시간이다.
  • 정렬된 배열의 이진탐색은 O(log⁡n)O(\log n)이다.
  • 반복문으로 피보나치 수를 구하면 O(n)O(n)이다.

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

이어서 풀어보기

[7급 국가직 자료구조론] 12년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요7급 국가직 자료구조론 기출문제 암기장 전체 보기