[CH7] 정렬과 탐색 // 분할 정복 결합

분할 정복 병합이란?

분할 : 큰 문제에서 반복 가능한 가장 작은 단위의 문제로 나누는 것.

정복 : 가장 작은 단위의 문제를 해결하는 것.

결합: 가장 작은 단위의 문제를 해결 후 결합하여 전체 문제를 해결하는 것.

 

종류)

병합 정렬

퀵 정렬

힙 정렬

 

병합 정렬의 시간복잡도 및 특징

퀵 정렬의 시간복잡도 및 특징

 

탐색

 

종류)

1) 선형 탐색

 

- 앞에서부터 순차적으로 탐색하는것.

- 시간 복잡도 : O(n)

 

2) 이진 탐색

- 정렬된 배열에 대하여 순차적으로 반으로 줄여가며 탐색하는 방법

- 시간 복잡도 : O(logn)

- 단, 해당 탐색을 하기 위해선 배열이 정렬되어 있어야만 한다.

 

-> 이진 탐색 사용 방법

 

<algolithm> 에 정의되어 있음.

 

함수 선언 내용

binary_search(array.begin(),array.end(),target);