합병정렬(merge sort)에 대한 설명으로 옳지 않은 것은? | [7급 국가직 자료구조론] 12년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 12년 1회차
합병정렬(merge sort)에 대한 설명으로 옳지 않은 것은?
1
점근분석(asymptotic analysis)할 때, 퀵정렬(quick sort)의 최악수행시간 보다 빠르다.
2
추가적인 메모리 사용없이 간단히 구현할 수 있다.
3
크기 n인 입력에 대한 최악수행시간을 T(n)이라 할 때, T(n)=2×T(n/2)+cnT(n) = 2 \times T(n/2) + cn으로 나타낼 수 있다. (단, c≥1c \ge 1 상수)
4
분할정복(divide and conquer) 기법을 사용한다.
해설

합병정렬은 병합 과정에서 입력 크기만큼의 추가 배열이 필요하므로, 추가 메모리 없이 구현할 수 있다는 설명이 옳지 않다.

정렬된 두 부분 배열을 합칠 때 결과를 임시 배열에 옮겨 적은 뒤 되돌려 놓는 방식이라 공간복잡도는 O(n)O(n)이다.

  • 합병정렬의 최악 시간은 O(nlog⁡n)O(n \log n)으로, 퀵정렬의 최악 O(n2)O(n^{2})보다 빠르다 — 옳다.
  • 절반씩 두 번 재귀 호출하고 병합에 선형 시간이 들어 T(n)=2T(n/2)+cnT(n) = 2T(n/2) + cn이 성립한다 — 옳다.
  • 분할 → 정복 → 결합 단계를 거치는 대표적인 분할정복 알고리즘이다 — 옳다.

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

이어서 풀어보기

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