[알고리즘/Week 6] Assignment 6

1. Solve the exercise problem 14 of the chapter 7.

문제 14번: 합병정렬 알고리즘에서 레코드의 저장 횟수를 기준으로 할 때 시간복잡도는 대략 T(n) = 2nlgn이 됨을 증명하시오.

 

   합병정렬에서 주어진 배열의 크기가 n이라고 하면, 배열을 반으로 나누는 과정에서 각각의 하위 배열에 n/2개씩 원소가 들어간다. 각각의 하위 배열에 대하여 현재 배열과 하위 배열의 정렬을 수행하고, 이를 합병하는 과정에서 새로운 배열을 생성하여 정렬된 레코드를 저장한다. 이때, 새로운 배열의 크기는 두 하위 배열의 크기를 합친 것과 같기 때문에, 각 하위 배열의 크기가 n/2인 경우, 새로운 배열에는 n개의 레코드가 저장된다.

   각각의 하위 배열에 대해 정렬하는 과정에서도 각 레코드는 최대 한 번씩 비교하면서 이동되며, 이동할 때마다 저장이 발생한다. 따라서, 하위 배열의 크기가 n/2일 때, 하위 배열을 정렬하는데 드는 저장 횟수는 대략 2(n/2)lg n이 된다.

 

T(n) = 2T(n/2) + 2(n/2)lgn

= 2(2T(n/4) + 2(n/4)lg(n/2)) + 2(n/2)lgn

= 4T(n/4) + 2nlgn

= 8T(n/8) + 3nlgn

= ...

= nT(1) + nlgn

T(1)은 상수 시간이므로 1과 같기 때문에 시간복잡도는 대략 T(n) = 2nlgn 이다.