반응형
재귀 알고리즘 설계를 기반으로 한다.
따라서
1. 탈출조건
2. 각 하위문제는 본문제보다 작은 문제여야한다.
위 두조건을 만족해야한다.
3단계로 간단히 말하면
1. 분할 : n크기의 배열을 n/2크기의 하위배열 2개로 나눔
2. 정복 : 배열의 크기 1이 될때까지 반복해 재귀적으로 정렬함.
3. 결합 : 하위배열을 합해서 정렬함.
시간 복잡도
1. 분할 : 중간값을 구함, (상수시간) O(1)
2. 정복 : 재귀 횟수는 트리의 level인 log2n임.
3. 결합 : 정렬된 하위배열 요소들을 한번씩 비교후 정렬함 O(n)
각 트리 계층마다 O(n)번의 연산을 하므로
시간복잡도는 트리의 level(재귀횟수) * O(n) 이다.
O(nlogn)
'알고리즘' 카테고리의 다른 글
| 정렬의 stability (0) | 2021.04.05 |
|---|---|
| algorithm, part1 | Coursera 과제 하는법 (mac) (0) | 2021.03.16 |
| quickSort 파이썬 구현 (백준 2750) (0) | 2021.03.10 |
| 15일차 - 똑똑똑똑똑 (0) | 2021.03.08 |
| 선택 정렬 시간복잡도 (0) | 2021.03.01 |
