합병정렬1 [알고리즘] Divide & Conquer (2) - Merge sort [2. Merge sort, 합병정렬] ※ 배열의 요소들을 정렬할 때 인접한 각 요소들을 비교하는 방식(bubble sort 등)의 성능 : O(n²) 따라서, 더 효율적일 수 있는 방법은 "분할정복" ● 방식 → 정렬되지 않은 상태로 나열된 요소들의 집합을 절반으로 나누고 → 각각의 분할된 집합을 정렬한 다음 → 다시 결합한다 ● 알고리즘 → Divide : m = (s+e)/2 를 기준으로 더이상 분할할 수 없을때까지 절반으로 분할 O(n) → Conquer : 더 이상 분할할 수 없을 때 원소가 하나인 집합이므로, 정렬된 것으로 간주 → Combine : 분할 후 각 집합들을 결합 O(logn) → Degenerate case : 원소가 하나인 경우 (s==e) (* 배열A내에 원소가 n개인 경우 .. 2022. 11. 8. 이전 1 다음