만약에 8개의 원소를 가지고 있는 리스트를 정렬해야 한다고 가정해봅시다.
이때도 \(\Theta(nlgn)\)인 merge sort가 \(\Theta(n^2)\)인 exchange sort보다 좋을까요?
아마 작은 분할일 때는 오히려 exchange sort가 좋지 않을까요?
merge sort가 더 좋다고 말하는 것은 n이 무한대로 갈 때의 얘기입니다.
오히려 n이 작으면 작을수록 다른 알고리즘이 더 좋을 때가 있습니다.
이때 나오는 것이 Threshold, 임계값입니다.
1. 임계값이란?
분할 정복 알고리즘이 A이고, 대체 알고리즘이 B라고 합시다.
계속해서 분할하다 보면 어느 순간부터 B가 더 좋아질 때가 있습니다.
바로 위의 sorting이 예시입니다.
이때, 대체 알고리즘이 더 좋아지는 시점이 Treshold입니다.
그러면 이 임계값은 어떻게 구하느냐?
A와 B의 실행 속도가 같아지는 지점이 임계값이라고 생각하실 수도 있습니다.
하지만 이는 틀렸습니다.
교환 정렬 시간 복잡도 < 합병 정렬 시간 복잡도
\(\frac{n(n-1)}{2} < 32n lgn\)
라고 생각하실 것 같습니다.
이를 계산하면 n < 591이라는 부등식을 얻을 수 있습니다.
하지만 이는 어떤 의미냐면 n = k 일때, 정렬을 한다고 가정했을 때,
만약에 n의 초깃값 k가 다음과 같은 범위 k < 591 라면 교환 정렬이 좋다는 뜻입니다.
하지만 저희가 알고 싶은 건 합병 정렬을 하다가 어느 순간 분할을 멈추고 그냥 교환 정렬을 하는 게 더 좋은 임계점입니다.
따라서 합병 정렬의 시간 복잡도를 있는 그대로 사용하여 계산하겠습니다.
재현식은 다음과 같습니다.
\(W(n)\, =\, \left\{\begin{matrix}
\frac{n(n-1)}{2} & (n\leq t) \\
W(\frac{n}{2})+W(\frac{n}{2})+32n & (n> t) \\
\end{matrix}\right.\)
이때, t의 최적 값을 구하려면 \(W(\frac{t}{2})+W(\frac{t}{2})+32t\,=\,\frac{t(t-1)}{2}\)를 계산하면 됩니다.
이렇게 계산하시다 보면 t = 128이 나옵니다.
이는 즉, Merge Sort를 하다가 원소의 개수가 128개 이하가 되면 Exchange Sort를 하는 게 더 좋다는 것을 의미합니다.
결론적으로 분할 정복 알고리즘 A와 대체 알고리즘 B의 속도가 같아지는 지점이 아닌, A와 B를 동시에 사용했을 때의 최적 값을 찾아야 합니다.
감사합니다.
지적 환영합니다.