N개의 원소를 가지는 배열을 합병 정렬(Merge Sort) 알고리즘으… | [7급 국가직 자료구조론] 08년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 08년 1회차
NN개의 원소를 가지는 배열을 합병 정렬(Merge Sort) 알고리즘으로 정렬하고자 한다. 이 알고리즘에서 값을 비교하는 횟수를 C(N)C(N)이라고 할 때, 순환식(recurrence equation)으로 표현된 C(N)C(N)과 시간복잡도는?
(단, N=2kN=2^k이고, C(1)=0C(1)=0이라고 가정한다)
C(N)C(N)  시간복잡도
1
C(N)=C(N/2)+N−1C(N)=C(N/2)+N-1  O(log⁡N)O(\log N)
2
C(N)=C(N/2)+1C(N)=C(N/2)+1  O(log⁡N)O(\log N)
3
C(N)=2C(N/2)+N−1C(N)=2C(N/2)+N-1  O(Nlog⁡N)O(N\log N)
4
C(N)=2C(N/2)+1C(N)=2C(N/2)+1  O(Nlog⁡N)O(N\log N)
해설

합병 정렬의 비교 횟수는 C(N)=2C(N/2)+N−1C(N)=2C(N/2)+N-1, 시간복잡도는 O(Nlog⁡N)O(N\log N)이다.

크기 N/2인 두 부분을 각각 정렬하고(2C(N/2)2C(N/2)), 정렬된 두 리스트를 합병할 때 최악 N−1N-1번 비교한다.

이를 풀면 C(N)=Nlog⁡2N−N+1C(N)=N\log_2 N-N+1이다.

  • C(N)=C(N/2)+N−1C(N)=C(N/2)+N-1: 한쪽 절반만 재귀하는 식으로 합병 정렬과 다르며, 풀면 O(N)O(N)이다.
  • C(N)=C(N/2)+1C(N)=C(N/2)+1: 이진 탐색의 비교 횟수 식이다.
  • C(N)=2C(N/2)+1C(N)=2C(N/2)+1: 합병 비용을 상수로 본 식이며, 풀면 O(N)O(N)이 되어 짝지은 복잡도와도 맞지 않는다.

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

이어서 풀어보기

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