합병정렬(merge sort)에 대한 설명으로 옳지 않은 것은? | [7급 국가직 자료구조론] 12년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 12년 1회차
합병정렬(merge sort)에 대한 설명으로 옳지 않은 것은?
1
점근분석(asymptotic analysis)할 때, 퀵정렬(quick sort)의 최악수행시간 보다 빠르다.
2
추가적인 메모리 사용없이 간단히 구현할 수 있다.
3
크기 n인 입력에 대한 최악수행시간을 T(n)이라 할 때, 으로 나타낼 수 있다. (단, 상수)
4
분할정복(divide and conquer) 기법을 사용한다.
해설
합병정렬은 병합 과정에서 입력 크기만큼의 추가 배열이 필요하므로, 추가 메모리 없이 구현할 수 있다는 설명이 옳지 않다.
정렬된 두 부분 배열을 합칠 때 결과를 임시 배열에 옮겨 적은 뒤 되돌려 놓는 방식이라 공간복잡도는 이다.
- 합병정렬의 최악 시간은 으로, 퀵정렬의 최악 보다 빠르다 — 옳다.
- 절반씩 두 번 재귀 호출하고 병합에 선형 시간이 들어 이 성립한다 — 옳다.
- 분할 → 정복 → 결합 단계를 거치는 대표적인 분할정복 알고리즘이다 — 옳다.
오류나 개정된 내용이 보이면 알려주세요