Determining Thresholds

2.7 Determining Thresholds

threshold 란? : 단순한 알고리즘보다 Strassen의 알고리즘을 사용하는 편이 더 좋을 것이라고 예상되는 지점

 

n-1 : merge할 때 걸리는 시간.

실험을 통해 알아내야 한다.

merge 알고리즘을 만든 다음에 넣어봐야 아는 것이다.

 

 

merge 할 때 시간 복잡도가 32 n 이라면

 

시간복잡도가 32n logn 는 merge sort 알고리즘 시간복잡도 이고

exchange sort 했을 때 n(n-1)/2 이다.

 

exchange sort 실행 시간 < merge sort 실행 시간인 지점을 봐보자.

 

이 부등식의 의미는 n=1 이 될 때까지 한 것.

---

 

등식보다  ≥ 부등식으로 풀어야 한다.

 

현재 배열의 사이즈 = t 개

t개의 원소를 t/2로 나눠서 각각을 exchange sorting 한 다음에 merge한 것 ≥ t개를 exchange sort 한 것

 

t가 짝수인 경우 128

t가 127이 되면 exchange sort 하는게 더 빠르다.

 

t가 홀수일 때

t/2의 floor = (t-1)/2

t/2의 ceiling = (t+1)/2

따라서 128이 안되면 merge sort 보단 그냥 exchange sort 하는게 좋다. 

 

---

lager integer multiplication에서 나온다.

 

이것의 optimal threshold를 구해보자.

 

t자리일 때 standard 알고리즘의 시간복잡도는 t^2이다.

t/2로 나눠서 걸리는 시간복잡도 좌항.

 

짝수일 때 t ≤ 64

홀수일 때 t ≤ 70.04

 

이때는 짝수일 때와 홀수일 때가 차이가 난다. 

standard 일 때 걸리는 시간 , 두개로 나눠서 standard 곱셈을 한 다음에 결합했을 때 걸리는 시간

 

자리수가 짝수인 경우 64보다 작으면 divide 하지 않고 standard로 곱하는게 더 빠르다.

자리수가 홀수인 경우 70보다 작으면 divide 하지 않고 standard로 곱하는게 더 빠르다.

자리수가 홀수인 경우 71인 경우에는 divide 하는 것이 더 빠르다. 69인 경우에는 standard로 곱하는 것이 더 빠르다.