쉽게 배우는 알고리즘(문병로) Ch4 병합정렬 연습문제
조회수 433회
문제 : 병합 정렬에서 둘로 나누는 대신 16개로 나누어도 정렬은 된다. 즉, 최상위 레벨에서 병합 정렬을 16번 부른 다음 병합을 한다. 이 경우 알고리즘을 기술하고 점근적 복잡도를 분석하시오. 병합 부분을 효율적으로 하는 자료구조와 방법도 기술에 포함하시오.
점근적 복잡도 분석은 재귀식과 마스터 정리를 활용하여 해결했습니다. 병합 부분을 효율적으로 하는 자료구조가 무엇인지 궁금합니다. 저의 직관으로는 트리일 것 같은데 이유를 잘 모르겠습니다.
댓글 입력