-
n개의 원소가 존재 할때
원소들을 절반으로 배열1 , 배열2로 나누어 각각 정렬한 후
배열1과 배열2의 원소들을 각각 비교하여 정렬하면서 배열1과 배열2를 합친다.
이때 배열1과 배열2를 정렬하는 과정은 재귀함수 2개로 구현하고
정렬된 배열1과 배열2를 합치는 과정을 merging이라는 함수로 구현한다.
배열의 원소의 개수가 1이 될 때가 기저 조건이다.
기저 조건일때는 merging을 수행하지 않고 return한다.
(merging 함수를 구현할때는 인수를 4개를 받는데 배열1과 배열2의 첫 번째 인덱스와 마지막 인덱스를 입력받는다.)
시간 복잡도
합병정렬의 시간복잡도는 재귀함수를 고려하여 계산한다.
T(n) = 왼쪽 정렬 시간복잡도 + 오른쪽 정렬 시간복잡도
+ 정렬된 왼쪽 배열과 정렬된 오른쪽 배열을 합치는 시간복잡도
왼쪽 정렬 시간복잡도 = 오른쪽 정렬 시간복잡도 = T(n/2)
정렬된 왼쪽 배열과 정렬된 오른쪽 배열을 합치는 시간복잡도 = O(n-1) = O(n)
//n개의 인덱스에 오는 원소들을 결정하기 위해 왼쪽 배열과 오른쪽 배열을 n-1번 비교하기 때문이다.
따라서 T(n) = 2*T(n/2) + O(n)
위의 식을 점화식이라고 부른다.
T(n) = 2*{2*T(n/4) + O(n/2)} + O(n) = 4*T(n/4) + 2*O(n/2) + O(n) = 4*T(n/4) + 2*O(n)
[1번 대입하여 계산하였을때]
따라서 n이 1로 나누어 떨어질 때까지 나누어야하므로 (logn)/(log2) 번 나눠야 한다.
[ex n이 64면 (log64)/(log2)가 6이므로 6번 나누면 된다.]
k번 대입하였을때는 아래와 같다.
T(n) = 2^(k+1)*T( n/2^(k+1) ) + (k+1)*O(n)
k+1=(logn)/(log2) 일때 T(1)이 되므로 오른쪽에서 T가 사라진다.
T(n) = 2^{(logn)/(log2)}*1 + (logn)/(log2)*O(n)
이때 2^{(logn)/(log2)}*1 ==n 는 (logn)/(log2)*O(n)에 비해 극한으로 보내었을 때 값이 현저하게 작으므로 무시된다.
따라서 T(n) = (logn)/(log2)*O(n)이 된다.
728x90