(분할정복 알고리즘)
병합정렬
시간복잡도
n ----------->ex: 4
n/2 n/2 ------------> 2
n/2의2승 n/2의2승 n/2의2승 n/2의2승 ------> 1
각 단계(수평)는 2의 i승 * n/2의 i승 = O(n)
단계는(수직) log n개 만큼 만들어짐. O(log n) 상수2삭제
O(n)* O(logn) = O(n logn)
분리하는 함수 / 병합하는 함수
샘플 : 49 97 53 5 33 65 62 51
split 단계
49 97 53 5 33 65 62 51
49 97 53 5 33 65 62 51
49 97 53 5 33 65 62 51
--------------------------------------------------------
merge단계
49 97 5 53 33 65 51 62
5 49 53 97 33 51 62 65
5 33 49 51 53 62 65 97
'코딩테스트 준비 > 알고리즘' 카테고리의 다른 글
| [알고리즘]순차탐색 with Python (0) | 2022.05.06 |
|---|---|
| [알고리즘]이진탐색 with Python (0) | 2022.05.06 |
| [알고리즘]퀵소트 with Python (0) | 2022.05.06 |
| [알고리즘]재귀함수 with Python (0) | 2022.05.05 |
| [알고리즘]선택정렬 with Python (0) | 2022.05.04 |
