Computer Science/알고리즘

[알고리즘] 임계값의 결정 (Determining Thresholds)

바보1 2022. 4. 5. 19:46

만약에 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를 동시에 사용했을 때의 최적 값을 찾아야 합니다.

 

 

감사합니다.

 

 

 

지적 환영합니다.