Merge Sort 시간 복잡도

T(Divide) = 0 이다. 

진짜야. Divide에 시간이 안 걸린다는 뜻이다. 지난번 탐색알고리즘에서는 탐색하는 과정에서 비교연산을 해야하기때문에

 

그냥 직접적으로 S[0] 부터 S[n/2] 까지, S[n/2+ 1]부터 S[n]까지 식으로 해당 인덱스만 기억하면 되는 것이다.

물론 코드로 이렇게 인덱스를 바로 기억하도록 짜려면 상당히 어려울 것이지만...

엄밀히는 Copy는 반드시 필요한 과정은 아니기 때문에 시간복잡도 분석에서 제외된다.

 

T(Solve) = 2 * T(n/2) 이 맞다. 왼쪽, 오른쪽 자른 놈들을 다시 해결하는데 걸리는 시간을 계산하면 되기때문에 각각

T(n/2)(왼쪽) + T(n/2)(오른쪽) 을 더하면 2 * T(n/2)이 되는 것이다.

​

T(Combine) = n - 1 이다. 왼쪽 오른쪽을 갈라놓고, 하나하나 비교하는 연산을 하면, 최악의 경우 n/2 + (n/2 -1)이 된다.

-1이 되는 이유는 맨 마지막 한 놈은 그냥 내려오기 때문이다. 따라서 정리하면 T(Combine) = n - 1 이다.

​

n이 매우 큰 수라고 가정한다. n = 2^k or 2^k + 1 (짝수, 홀수 둘 다 될 수 있으므로, 하지만 1이 거의 의미가 없다. 따라서 그냥 편의상 n = 2^k라고 가정하자)

그리고 식을 정리하면,

= n*T(1) + nlogn이 된다. 마지막으로 큰 실수를 하면 안되는게, 지난번 탐색알고리즘 처럼 생각하고 T(1) = 1 이라고 하면 안된다!

지금은 '탐색'이 아닌 '정렬'을 하고있고, 1개의 데이터를 정렬하는 시간은 0초이다. 1개를 탐색할때는 비교를 1번 해야하니까 1이고.

따라서 T(1)이 0이므로, 최종적으로 식을 정리하면

 

 

마스터 정리 Master Theorem 알고리즘 시간 복잡도 구하기

 

<알고리즘> 03 - 병합정렬(Merge Sort)