HW#03 : 분할을 두 개로 하는 경우가 많다. 왜 두 개를 사용하는가?

Divide and Conquer Approach를 보면 Binary Search와 2-Way Merge Sort와 같이 세 개가 아닌 두 개를 사용하는 경우가 많다. 왜 두개를 사용하는가?

K-Way Merge Sort를 예로 들어 보면 K값을 3으로 할 수도 있고 2로 할 수도 있다. 2-Way Merge Sort와 3-Way Merge Sort의 시간복잡도(Time Complexity)를 생각해 보아야 한다. Divide and Conquer Approach의 경우 T(n) = Divide + Conquer + Combie 시간을 생각해 보아야 한다.

K = 2 인 경우, T(n) = 0 + T(n/2) + T(n/2) + n/2 + n/2 - 1

K = 3 인 경우, T(n) = 0 + T(n/3) + T(n/3) + T(n/3) + n/3 + n/3 + n/3 - 1

결국 입력 원소의 개수가 크다면 K 값이 큰 것이 되부름(Recursion)을 적게 하여 유리하다. 또한 병렬 처리를 할 경우 K 값이 큰 것이 좋다. 하지만 3-Way Merge Sort는 병합 과정이 복잡하기 때문에 메모리의 Activation Record를 낭비해서라도 2-Way Merge Sort를 사용한다.