[CS50] 합병 정렬, 이진 탐색

edwith CS50강의를 보며 정리했습니다.

---

합병정렬

합병정렬은 원소가 한개가 될 때까지 계속 반으로 나누다가 다시 합쳐나가며 정렬을 하는 방식이다.

합병 정렬은 버블 정렬, 선택 정렬, 삽입 정렬보다 훨씬 빠르고 간결하고 깔끔하게 표현할 수 있다.

합병정렬의 시간복잡도 상한선은 $nlogn$이다. 다른 정렬의 최소 상한선은 $n^2$이고, 이는 $nlogn$보다 크다. 합병정렬은 시간적으로 빠르지만 단점도 존재한다.

합병 정렬은 더 많은 공간(메모리)을 사용한다. 

8개의 자료가 있다고 하면, 세 번을 나눈다. $log28$은 3이다. 그리고 그 한번을 실행할 때마다 자료를 n번씩 봐야했기 때문에 $nlogn$으로 표현할 수 있다. 합병 정렬은 병합하는 알고리즘을 포함한다.

실행시간으로 표현을 한다면, $T(n) = T(\frac{n}{2}) + T(\frac{n}{2}) + O(n) $ 이 될 수 있다. 각 $ T(\frac{n}{2}) $는 왼쪽과 오른쪽 절반에 해당하고, $O(n)$ 은 자료를 비교하는 n 단계를 나타낸다.

 

이진탐색

전화번호부 예시처럼 봐야하는 데이터의 목록이 점점 작아지도록 계속해서 절반으로 나누는 알고리즘의 시간복잡도는 $logn$이다. $logn$에서 실행하는 알고리즘의 세부 조건은 알고리즘 입력 목록이 정렬되는 것을 가정해야 한다.

이진 탐색을 일반적으로 선형 탐색보다 속도가 빠르지만, 배열을 정리하는 시간이 추가되기도 한다.