[알고리즘 / 분할정복] #1 합병 정렬 (Merge Sort)
합병 정렬 (Merge Sort) 입력값을 $1/2$로 분할하여 부분문제 크기를 감소시키는 분할 정복 알고리즘이다. N개의 숫자의 배열을 N/2개씩 분할하고 재귀적 합병 정렬 후, 2개의 정렬된 부분을 합병하여 정렬한다. 즉, 합병 과정이 문제를 정복하는 것이다. 시간복잡도 합병 정렬은 분할 후 합병이 일어난다. 먼저 분할은 배열을 더이상 나눌서 없을때까지 2개의 배열로 나누는 재귀함수를 호출하는 것으로 O(1)의 시간이 걸린다. 이후 합병으로 넘어가면 2개의 정렬된 배열 A(크기 m개)와 B(크기n개)를 받으면 최대 비교 횟수는 (m+n-1)번이다. 합병시 두개의 숫자를 한번씩 비교할때, 더 작은 수가 결과 배열인 C에 저장된다. 따라서 배열 C는 A와 B의 모든 수(m+n)의 숫자들이 저장되나, 가장..
Computer/Algorithm
2021. 4. 16. 20:01
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- 구조
- static_cast
- 포인터
- 초기화
- 클래스
- 함수
- 명령어
- 컴파일
- New
- dynamic_cast
- 프로세스
- 백준
- 게임수학
- CPU
- 입출력
- 인터럽트
- 메모리
- const
- c++
- thread
- 스레드
- 알고리즘
- 운영체제
- 할당
- 수학
- 상속
- 멀티스레드
- 레지스터
- malloc
- 크기
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
글 보관함