이진탐색 vs 합병정렬

교수님

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

날카롭고 좋은 질문이네요.

이진 탐색과 합병 정렬은 목적과 대상이 다르니 비교가 불가능한 것이 맞습니다.

다만, 분할 정복의 시간 복잡도라는 측면에서 보면,

이진 탐색은 탐색 공간을 한 번에 절반으로 줄여나가는 알고리즘이고,

합병 정렬(또는 퀵 소트)은 탐색 공간을 한 번에 절반으로 나누지만, 

결국 분할된 양쪽 다 정복을 해야 하는 알고리즘입니다.

즉, Divide 자체가 Conquer가 되어 솔루션을 바로 찾는 알고리즘과,

Divide - Conquer를 한 후에 Combine을 통해서 솔루션을 찾을 수 있는 알고리즘을 비교하면,

둘 사이에는 커다란 시간 복잡도 차이가 있다는 뜻입니다.

좀 더 정확히 표현하면, 

이진 탐색 "문제"와 (합병/퀵) 정렬 "문제"의 시간 복잡도에 차이가 있다,

특히, 이런 경우에는 lower bound 시간 복잡도가 차이가 있다,

라고 해석하시면 되겠습니다.