정렬된 N개의 데이터를 처리하는 데 0(NlogN)의 시간이 소요되는 정렬 알고리즘은?
정답 1번
합병 정렬은 데이터를 절반씩 분할한 뒤 정렬된 부분 배열을 병합합니다. 분할 단계가 log₂N개이고 각 단계에서 전체 N개 원소를 비교·복사하므로 시간 복잡도는 입력 상태와 무관하게 O(N log N)입니다.
콘텐츠 정보
- 자료 유형
- 편집복원
- 검수 상태
- 내용 검수 완료
- 해설 작성·검수
- 정처LAB 편집 기준
- 최종 검수
- 2026-08-21
합병 정렬은 데이터를 절반씩 분할한 뒤 정렬된 부분 배열을 병합합니다. 분할 단계가 log₂N개이고 각 단계에서 전체 N개 원소를 비교·복사하므로 시간 복잡도는 입력 상태와 무관하게 O(N log N)입니다.