-
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
이진탐색 vs 합병정렬
20.10.29 08:13 작성 조회수 250
1
이진탐색이 합병정렬보다 낫다는게 잘 이해가 안됩니다.
이진탐색은 sorted list 안에 요소 x 가 있는지 찾는 searching 알고리즘이고 합병정렬은 unsorted list 를 sorted list 로 만드는 sorting 알고리즘이니, 사실상 둘은 비교가 불가능한게 아닌가요 ?
답변을 작성해보세요.
1
1
주니온
지식공유자2020.10.29
날카롭고 좋은 질문이네요.
이진 탐색과 합병 정렬은 목적과 대상이 다르니 비교가 불가능한 것이 맞습니다.
다만, 분할 정복의 시간 복잡도라는 측면에서 보면,
이진 탐색은 탐색 공간을 한 번에 절반으로 줄여나가는 알고리즘이고,
합병 정렬(또는 퀵 소트)은 탐색 공간을 한 번에 절반으로 나누지만,
결국 분할된 양쪽 다 정복을 해야 하는 알고리즘입니다.
즉, Divide 자체가 Conquer가 되어 솔루션을 바로 찾는 알고리즘과,
Divide - Conquer를 한 후에 Combine을 통해서 솔루션을 찾을 수 있는 알고리즘을 비교하면,
둘 사이에는 커다란 시간 복잡도 차이가 있다는 뜻입니다.
좀 더 정확히 표현하면,
이진 탐색 "문제"와 (합병/퀵) 정렬 "문제"의 시간 복잡도에 차이가 있다,
특히, 이런 경우에는 lower bound 시간 복잡도가 차이가 있다,
라고 해석하시면 되겠습니다.
답변 2