이진탐색 vs 합병정렬

Question

이진탐색이 합병정렬보다 낫다는게 잘 이해가 안됩니다. 이진탐색은 sorted list 안에 요소 x 가 있는지 찾는 searching 알고리즘이고 합병정렬은 unsorted list 를 sorted list 로 만드는 sorting 알고리즘이니, 사실상 둘은 비교가 불가능한게 아닌가요 ?

델서호린더하웃 · Answer

교수님 빠른 답변 감사합니다. 복잡도라는 개념을 이해하는데 이번 강의가 큰 도움이 되었습니다.

주니온 · Answer

날카롭고 좋은 질문이네요. 이진 탐색과 합병 정렬은 목적과 대상이 다르니 비교가 불가능한 것이 맞습니다. 다만, 분할 정복의 시간 복잡도라는 측면에서 보면, 이진 탐색은 탐색 공간을 한 번에 절반으로 줄여나가는 알고리즘이고, 합병 정렬(또는 퀵 소트)은 탐색 공간을 한 번에 절반으로 나누지만,  결국 분할된 양쪽 다 정복을 해야 하는 알고리즘입니다. 즉, Divide 자체가 Conquer가 되어 솔루션을 바로 찾는 알고리즘과, Divide - Conquer를 한 후에 Combine을 통해서 솔루션을 찾을 수 있는 알고리즘을 비교하면, 둘 사이에는 커다란 시간 복잡도 차이가 있다는 뜻입니다. 좀 더 정확히 표현하면,  이진 탐색 "문제"와 (합병/퀵) 정렬 "문제"의 시간 복잡도에 차이가 있다, 특히, 이런 경우에는 lower bound 시간 복잡도가 차이가 있다, 라고 해석하시면 되겠습니다.