Merge Sort1 Merge Sort (병합 정렬) Merge Sort는 전형적인 분할 정복(divide and conquer) 알고리즘의 하나입니다. 시간복잡도 O(n^2)을 가지는 일반적인 정렬과 달리 Merge Sort의 시간 복잡도는 O(nlog_2 n) 이 됩니다. 이등분씩 나누는 것을 반복해서 최소 단위까지 분할합니다. (divide) 분할한 부분 리스트를 정렬합니다. (conquer) 정렬된 부분 리스트들을 하나의 리스트에 병합합니다. (combine) 다음은 swift 언어로 구현한 divide, merge 메서드 입니다. func divide(_ start: Int,_ end: Int) { if start >= end { return } let mid = (start + end) / 2 divide(start, mid) divide(mid.. 2021. 2. 11. 이전 1 다음
